Submission #138471

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138471	2019-07-30T05:02:25 Z	송준혁(#3322)	Non-boring sequences (CERC12_D)	C++14	1 / 1	1144 ms	12668 KB

D

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int TC, N;
int A[202020];
int L[202020], R[202020];
map<int, int> M;

bool f(int s, int e){
	if (e < s) return true;
	for (int i=0; i<=(e-s)/2; i++){
		if (L[s+i] < s && e < R[s+i]) return f(s, s+i-1) && f(s+i+1, e);
		if (L[e-i] < s && e < R[e-i]) return f(s, e-i-1) && f(e-i+1, e);
	}
	return false;
}

int main(){
	scanf("%d", &TC);
	while (TC--){
		scanf("%d", &N);
		for (int i=1; i<=N; i++) scanf("%d", &A[i]);
		
		for (int i=1; i<=N; i++) L[i] = 0, R[i] = 1234567890;
		M.clear();
		for (int i=1; i<=N; i++){
			if (M.find(A[i]) != M.end()) L[i] = M[A[i]];
			M[A[i]] = i;
		}
		M.clear();
		for (int i=N; i>=1; i--){
			if (M.find(A[i]) != M.end()) R[i] = M[A[i]];
			M[A[i]] = i;
		}
		
		puts(f(1, N) ? "non-boring" : "boring");
	}
	return 0;
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &TC);
  ~~~~~^~~~~~~~~~~
D.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
D.cpp:24:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=1; i<=N; i++) scanf("%d", &A[i]);
                            ~~~~~^~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	1096 KB	Output is correct
2	Correct	362 ms	4424 KB	Output is correct
3	Correct	623 ms	12668 KB	Output is correct
4	Correct	385 ms	10616 KB	Output is correct
5	Correct	1144 ms	6744 KB	Output is correct
6	Correct	425 ms	2832 KB	Output is correct
7	Correct	298 ms	2844 KB	Output is correct