oj.uz

Submission #633883

# Submission time Handle Problem Language Result Execution time Memory
633883 2022-08-23T11:16:39 Z lovrot Nice sequence (IZhO18_sequence) C++11
34 / 100
 2000 ms 2240 KB 
#include <bits/stdc++.h> 

#define pb push_back 
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;

const int N = 2 * 1e5 + 10;

int t, n, m, p[N], ans;
int pos;
int cyc[N], bio[N], ts[N], cookie;

bool cycp(int u){
	bio[u] = cookie;
	cyc[u] = cookie;
	// cout << u << "\n";
	int lv = u - m, uv = u + n;
	if(lv >= 0){
		if(cyc[lv] == cookie) 
			return true;
		if(cycp(lv))
			return true;	
	}
	if(uv <= ans){
		if(cyc[uv] == cookie) 
			return true;
		if(cycp(uv))
			return true;	
	}
	cyc[u] = -cookie;
	return false;
}

void topSort(int u){ 
	ts[u] = cookie;
	int lv = u - m, uv = u + n;
	if(lv >= 0){
		if(ts[lv] != cookie) topSort(lv);
	}
	if(uv <= ans){ 
		if(ts[uv] != cookie) topSort(uv);
	}
	p[u] = ++pos;
}

void output(){ 
	for(int i = 0; i <= ans; i++)
		if(ts[i] != cookie) topSort(i);

	printf("%d\n", ans);
	for(int i = 1; i <= ans; i++) 
		printf("%d ", (p[i] - p[0]) - (p[i - 1] - p[0]));
	printf("\n");
}

bool probaj(){ 
	pos = -1;
	cookie++;

	for(int i = 0; i <= ans; i++){ 
		if(bio[i] != cookie){
			if(cycp(i))
				return false;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	
	scanf("%d", &t);

	while(t--){ 
		scanf("%d %d", &n, &m);

		int lo = 0, hi = (n + m) + 1;
		while(hi - lo > 1){ 
			int mi = (lo + hi) / 2;
			ans = mi;
			if(probaj())
				lo = mi;
			else 
				hi = mi;
		}
		ans = lo;
		probaj();
		output();
	}
	return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~
sequence.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 212 ms 448 KB Ok
7 Execution timed out 2053 ms 1044 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Execution timed out 2069 ms 2240 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 0 ms 340 KB Ok
19 Correct 1 ms 340 KB Ok
20 Correct 0 ms 340 KB Ok
21 Correct 1 ms 340 KB Ok
22 Correct 0 ms 340 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 5 ms 340 KB Ok
25 Correct 3 ms 340 KB Ok
26 Correct 5 ms 340 KB Ok
27 Correct 3 ms 340 KB Ok
28 Correct 3 ms 340 KB Ok
29 Correct 3 ms 340 KB Ok
30 Correct 3 ms 340 KB Ok
31 Correct 3 ms 340 KB Ok
32 Correct 3 ms 340 KB Ok
33 Correct 4 ms 340 KB Ok
34 Correct 21 ms 624 KB Ok
35 Correct 30 ms 656 KB Ok
36 Correct 90 ms 704 KB Ok
37 Correct 28 ms 700 KB Ok
38 Correct 31 ms 716 KB Ok
39 Correct 23 ms 684 KB Ok
40 Correct 38 ms 716 KB Ok
41 Correct 35 ms 624 KB Ok
42 Correct 27 ms 724 KB Ok
43 Correct 28 ms 676 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 1 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 212 ms 448 KB Ok
19 Execution timed out 2053 ms 1044 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 1 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 212 ms 448 KB Ok
19 Execution timed out 2053 ms 1044 KB Time limit exceeded
20 Halted 0 ms 0 KB -