結果

問題 No.832 麻雀修行中
コンテスト
ユーザー torisasami4
提出日時 2019-06-14 17:10:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 3,910 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 77,476 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2024-11-08 01:46:15
合計ジャッジ時間 2,093 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:96:30: warning: iteration 10 invokes undefined behavior [-Waggressive-loop-optimizations]
   96 |                         c[i] = 0;
      |                         ~~~~~^~~
main.cpp:95:31: note: within this loop
   95 |                 for (i = 1; i < 12; i++)
      |                             ~~^~~~
main.cpp:96:30: warning: ‘void* __builtin_memset(void*, int, long unsigned int)’ writing 44 bytes into a region of size 40 overflows the destination [-Wstringop-overflow=]
   96 |                         c[i] = 0;
      |                         ~~~~~^~~
main.cpp:92:35: note: at offset 4 into destination object ‘c’ of size 44
   92 |                 int i, j, k,l,ck, c[11],flag1,flag2,count;
      |                                   ^

ソースコード

diff # 

	#include<iostream>
	#include<algorithm>
	#include<vector>
	#include<queue>
	#include<list>
	#include<set>
	#include<string>
	using namespace std;
	int gcd(int a, int b) {
		int c = a % b;
		while (c != 0) {
			a = b;
			b = c;
			c = a % b;
		}
		return b;
	}
	struct UnionFind {
		vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

		UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
			for (int i = 0; i < N; i++) par[i] = i;
		}

		int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
			if (par[x] == x) return x;
			return par[x] = root(par[x]);
		}

		void unite(int x, int y) { // xとyの木を併合
			int rx = root(x); //xの根をrx
			int ry = root(y); //yの根をry
			if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
			par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		}

		bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
			int rx = root(x);
			int ry = root(y);
			return rx == ry;
		}
	};
	typedef long long ll;

	ll M = 1000000007;

	vector<ll> fac(300001); //n!(mod M)
	vector<ll> ifac(300001); //k!^{M-2} (mod M)

	ll mpow(ll x, ll n) {
		ll ans = 1;
		while (n != 0) {
			if (n & 1) ans = ans * x % M;
			x = x * x % M;
			n = n >> 1;
		}
		return ans;
	}
	ll comb(ll a, ll b) {
		if (a == 0 && b == 0)return 1;
		if (a < b || a < 0)return 0;
		ll tmp = ifac[a - b] * ifac[b] % M;
		return tmp * fac[a] % M;
	}
	// mod. m での a の逆元 a^{-1} を計算する
	long long modinv(long long a) {
		long long b = M, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= M;
		if (u < 0) u += M;
		return u;
	}
	vector<vector<ll>> mul(vector<vector<ll>> a,vector<vector<ll>> b,int n){
		int i,j,k,t;
		vector<vector<ll>> c(n);
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				t = 0;
				for (k = 0; k < n; k++)
					t = (t + a[i][k]*b[k][j] % M)%M;
				c[i].push_back(t);
			}
		}
		return c;
	}
	int main() {
		char s[22];
		int i, j, k,l,ck, c[11],flag1,flag2,count;
		queue<int> que;
		cin >> s;
		for (i = 1; i < 12; i++)
			c[i] = 0;
		for (i = 0; s[i] != '\0'; i++)
			c[s[i]-'0']++;
		for (i = 1; i <= 9; i++) {
			if (c[i] <= 3) {
				c[i]++;
				flag1 = 1;
				for (j = 1; j <= 9; j++)
					if (c[j] != 0 && c[j] != 2)
						flag1 = 0;
				for (j = 1; j <= 9; j++) {
					if (flag1 == 0) {
						if (c[j] >= 2) {
							c[j] -= 2;
							for (k = 0; k < 512; k++) {
								if (flag1 == 0) {
									ck = k;
									l = 1;
									flag2 = 1;
									count = 0;
									while (ck > 0) {
										if (ck % 2 == 1) {
											if (c[l] >= 3) {
												c[l] -= 3;
												count++;
											}
											else {
												flag2--;
												break;
											}
										}
										l++;
										ck /= 2;
									}
									if (flag2 > 0) {
										for (l = 1; l <= 9; l++) {
											while (c[l] > 0 && c[l + 1] > 0 && c[l + 2] > 0) {
												c[l]--;
												c[l + 1]--;
												c[l + 2]--;
												que.push(l);
											}
											if (c[l] > 0) {
												flag2--;
												break;
											}
										}
										if (flag2 > 0)
											flag1++;
										while (!que.empty()) {
											c[que.front()]++;
											c[que.front() + 1]++;
											c[que.front() + 2]++;
											que.pop();
										}
									}
									ck = k;
									l = 1;
									while (ck > 0) {
										if (ck % 2 == 1) {
											if (count > 0) {
												c[l] += 3;
												count--;
											}
											else
												break;
										}
										l++;
										ck /= 2;
									}
								}
							}
							c[j] += 2;
						}
					}
				}
				c[i]--;
				if (flag1 > 0)
					cout << i << endl;
			}
		}
	}
0