Submission #138522

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138522	2019-07-30T06:09:13 Z	윤교준(#3320)	Who wants to live forever? (CERC12_B)	C++14	0 / 1	13 ms	760 KB

B

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 200055;

int A[MAXN];
char B[MAXN];

int T, N;

void run() {
	cin >> B;
	N = strlen(B);
	for(int i = 0; i < N; i++) A[i] = B[i]&1;

	{
		bool flag = false;
		for(int i = 0; i < N; i++) if(A[i]) flag = true;
		if(!flag) {
			puts("DIES");
			return;
		}
	}

	{
		for(int i = 0;; i++) {
			if((1<<i)-1 > N) break;
			if((1<<i)-1 == N) {
				puts("DIES");
				return;
			}
		}
	}

	if(N&1) {
		bool flag = false;
		for(int i = 0; i < N; i++)
			if(A[i] == (i&1)) {
				flag = true;
				break;
			}
		if(!flag) {
			puts("DIES");
			return;
		}
	}

	int mnk = N+1, t = -1;
	for(int k = 0;; k++) {
		if((1<<k) > N) break;
		int l = N - (1<<k);
		if(l % ((1<<k)+1)) continue;
		l /= (1<<k) + 1;
		int okt = -1;
		for(int t = 0;; t++) {
			if((1<<t)-1 > l) break;
			if((1<<t)-1 == l) {
				okt = t;
				break;
			}
		}
		if(okt < 0) continue;
		mnk = k; t = okt;
		break;
	}

	if(0 <= t) {
		int k = mnk;
		bool flag = false;
		for(int i = 0, idx = 0; i < (1<<k); i++) {
			idx += 1<<t;
			if(A[idx-1]) {
				flag = true;
				break;
			}
		}
		if(flag) {
			puts("LIVES");
			return;
		}
		for(int i = 1, s, e; i <= (1<<k); i++) {
			s = (1<<t) * i;
			e = s + (1<<t)-2;
			if(i&1) {
				for(int j = 0; j < (1<<t)-1; j++) {
					if(A[(1<<t)-j-2] != A[s+j]) {
						puts("LIVES");
						return;
					}
				}
			} else {
				for(int j = 0; j < (1<<t)-1; j++)
					if(A[j] != A[s+j]) {
						puts("LIVES");
						return;
					}
			}
		}
		puts("DIES");
		return;
	}
	puts("LIVES");
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(cin >> T; T--;) run();
	return 0;
}

Compilation message

B.cpp: In function 'void run()':
B.cpp:86:21: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   for(int i = 1, s, e; i <= (1<<k); i++) {
                     ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	13 ms	760 KB	Output is correct
4	Incorrect	3 ms	376 KB	Output isn't correct
5	Halted	0 ms	0 KB	-