Submission #138468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138468	2019-07-30T04:57:57 Z	이온조(#3319)	Non-boring sequences (CERC12_D)	C++14	1 / 1	2927 ms	78524 KB

D

#include <bits/stdc++.h>
using namespace std;
using mii = map<int, int>;
#define X first
#define Y second

int A[200009];
vector<int> S[200009];
bool ok;

int findany(int v, int s, int e) {
	int ret = *lower_bound(S[v].begin(), S[v].end(), s);
	assert(s <= ret && ret <= e);
	return ret;
}

void solve(int s, int e, mii &mp, set<int> &O) {
	if(s > e) return;
	if(O.empty()) {
		ok = 0;
		return;
	}
	int u = *O.begin(), p = findany(u, s, e);
	O.erase(O.begin()); mp.erase(u);
	int m = s+e >> 1;
	mii _mp; set<int> _O;
	if(p <= m) {
		for(int i=s; i<p; i++) {
			++_mp[A[i]];
			int v = --mp[A[i]];
			if(v == 1) O.insert(A[i]);
			if(v == 0) {
				O.erase(A[i]);
				mp.erase(A[i]);
			}
		}
		for(auto& it: _mp) if(it.Y == 1) _O.insert(it.X);
		solve(s, p-1, _mp, _O);
		solve(p+1, e, mp, O);
	}
	else {
		for(int i=p+1; i<=e; i++) {
			++_mp[A[i]];
			int v = --mp[A[i]];
			if(v == 1) O.insert(A[i]);
			if(v == 0) {
				O.erase(A[i]);
				mp.erase(A[i]);
			}
		}
		for(auto& it: _mp) if(it.Y == 1) _O.insert(it.X);
		solve(s, p-1, mp, O);
		solve(p+1, e, _mp, _O);
	}
}

int main() {
	int T; scanf("%d",&T);
	while(T--) {
		vector<int> T;
		int N; scanf("%d",&N);
		for(int i=1; i<=N; i++) {
			scanf("%d",&A[i]);
			T.push_back(A[i]);
		}
		sort(T.begin(), T.end()); T.resize(unique(T.begin(), T.end()) - T.begin());
		mii mp; set<int> O;
		for(int i=1; i<=T.size(); i++) {
			S[i].clear();
			S[i].shrink_to_fit();
		}
		for(int i=1; i<=N; i++) {
			A[i] = lower_bound(T.begin(), T.end(), A[i]) - T.begin() + 1;
			S[A[i]].push_back(i);
			++mp[A[i]];
		}
		for(auto& it: mp) if(it.Y == 1) O.insert(it.X);
		ok = 1; solve(1, N, mp, O);
		puts(ok ? "non-boring" : "boring");
	}
	return 0;
}

Compilation message

D.cpp: In function 'void solve(int, int, mii&, std::set<int>&)':
D.cpp:25:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
D.cpp: In function 'int main()':
D.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<=T.size(); i++) {
                ~^~~~~~~~~~
D.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf("%d",&T);
         ~~~~~^~~~~~~~~
D.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N; scanf("%d",&N);
          ~~~~~^~~~~~~~~
D.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i]);
    ~~~~~^~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	250 ms	5880 KB	Output is correct
2	Correct	523 ms	20564 KB	Output is correct
3	Correct	2927 ms	78524 KB	Output is correct
4	Correct	319 ms	42572 KB	Output is correct
5	Correct	2908 ms	25192 KB	Output is correct
6	Correct	952 ms	9784 KB	Output is correct
7	Correct	870 ms	8800 KB	Output is correct