oj.uz

Submission #46507

# Submission time Handle Problem Language Result Execution time Memory
46507 2018-04-21T08:06:43 Z Bruteforceman Nice sequence (IZhO18_sequence) C++11
76 / 100
 2000 ms 34120 KB 
#include "bits/stdc++.h"
using namespace std;
int N, M;
vector <int> g[400010];
vector <int> solution;
int deg[400010];

bool good(int size) {
	for(int i = 0; i <= size; i++) {
		g[i].clear();
		deg[i] = 0;
	}
	for(int i = N; i <= size; i++) {
		g[i].push_back(i - N);
		++deg[i - N];
	}
	for(int i = 0; i <= size - M; i++) {
		g[i].push_back(i + M);
		++deg[i + M];
	}
	queue <int> Q;
	for(int i = 0; i <= size; i++) {
		if(deg[i] == 0) {
			Q.push(i);
		}
	}
	vector <int> v;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		v.push_back(x);
		for(auto i : g[x]) {
			--deg[i];
			if(deg[i] == 0) {
				Q.push(i);
			}
		}
	}
	if(v.size() == size + 1) {
		vector <int> pref (size + 1);
		solution.resize(size + 1);
		for(int i = 0; i < v.size(); i++) {
			if(v[i] == 0) {
				int cur = 0;
				for(int j = i-1; j >= 0; j--) {
					pref[v[j]] = --cur; 
				}
				cur = 0;
				for(int j = i+1; j < v.size(); j++) {
					pref[v[j]] = ++cur;
				}
				break;
			}
		}
		for(int i = 1; i <= size; i++) {
			solution[i] = pref[i] - pref[i - 1];
		}
		return true;
	}
	return false;
}

int search(int b, int e) {
	if(b == e) {
		return b;
	}
	int m = (b + e + 1) >> 1;
	if(good(m)) return search(m, e);
	else return search(b, m - 1);
}

int main(int argc, char const *argv[])
{
	int test;
	scanf("%d", &test);
	for(int cs = 1; cs <= test; cs++) {
		scanf("%d %d", &N, &M);		
		int ans = search(0, N + M - 1);
		good(ans);
		printf("%d\n", ans);
		for(int i = 1; i <= ans; i++) {
			printf("%d ", solution[i]);
		}
		printf("\n");
	}
	return 0; 
}

Compilation message

sequence.cpp: In function 'bool good(int)':
sequence.cpp:39:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(v.size() == size + 1) {
     ~~~~~~~~~^~~~~~~~~~~
sequence.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
sequence.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = i+1; j < v.size(); j++) {
                      ~~^~~~~~~~~~
sequence.cpp: In function 'int main(int, const char**)':
sequence.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &test);
  ~~~~~^~~~~~~~~~~~~
sequence.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);  
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9880 KB Ok
3 Correct 9 ms 9880 KB Ok
4 Correct 10 ms 9968 KB Ok
5 Correct 11 ms 9968 KB Ok
6 Correct 10 ms 9968 KB Ok
7 Correct 9 ms 10116 KB Ok
8 Correct 10 ms 10116 KB Ok
9 Correct 10 ms 10116 KB Ok
10 Correct 10 ms 10116 KB Ok
11 Correct 12 ms 10116 KB Ok
12 Correct 9 ms 10116 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10116 KB Ok
2 Correct 9 ms 10116 KB Ok
3 Correct 9 ms 10116 KB Ok
4 Correct 9 ms 10116 KB Ok
5 Correct 9 ms 10116 KB Ok
6 Correct 16 ms 10116 KB Ok
7 Correct 47 ms 10748 KB Ok
8 Correct 30 ms 10748 KB Ok
9 Correct 50 ms 10892 KB Ok
10 Correct 38 ms 10892 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10892 KB Ok
2 Correct 9 ms 10892 KB Ok
3 Correct 12 ms 10892 KB Ok
4 Correct 10 ms 10892 KB Ok
5 Correct 10 ms 10892 KB Ok
6 Correct 467 ms 20312 KB Ok
7 Correct 425 ms 20932 KB Ok
8 Correct 940 ms 23240 KB Ok
9 Correct 607 ms 23240 KB Ok
10 Correct 367 ms 23240 KB Ok
11 Correct 606 ms 23240 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9880 KB Ok
3 Correct 9 ms 9880 KB Ok
4 Correct 10 ms 9968 KB Ok
5 Correct 11 ms 9968 KB Ok
6 Correct 10 ms 9968 KB Ok
7 Correct 9 ms 10116 KB Ok
8 Correct 10 ms 10116 KB Ok
9 Correct 10 ms 10116 KB Ok
10 Correct 10 ms 10116 KB Ok
11 Correct 12 ms 10116 KB Ok
12 Correct 9 ms 10116 KB Ok
13 Correct 10 ms 10892 KB Ok
14 Correct 10 ms 10892 KB Ok
15 Correct 10 ms 10892 KB Ok
16 Correct 10 ms 10892 KB Ok
17 Correct 12 ms 10892 KB Ok
18 Correct 11 ms 10892 KB Ok
19 Correct 11 ms 10892 KB Ok
20 Correct 10 ms 10892 KB Ok
21 Correct 9 ms 10892 KB Ok
22 Correct 9 ms 10892 KB Ok
23 Correct 10 ms 10892 KB Ok
24 Correct 19 ms 23240 KB Ok
25 Correct 17 ms 23240 KB Ok
26 Correct 15 ms 23240 KB Ok
27 Correct 15 ms 23240 KB Ok
28 Correct 14 ms 23240 KB Ok
29 Correct 16 ms 23240 KB Ok
30 Correct 14 ms 23240 KB Ok
31 Correct 15 ms 23240 KB Ok
32 Correct 16 ms 23240 KB Ok
33 Correct 15 ms 23240 KB Ok
34 Correct 23 ms 23240 KB Ok
35 Correct 25 ms 23240 KB Ok
36 Correct 25 ms 23240 KB Ok
37 Correct 27 ms 23240 KB Ok
38 Correct 23 ms 23240 KB Ok
39 Correct 22 ms 23240 KB Ok
40 Correct 25 ms 23240 KB Ok
41 Correct 22 ms 23240 KB Ok
42 Correct 24 ms 23240 KB Ok
43 Correct 23 ms 23240 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9880 KB Ok
3 Correct 9 ms 9880 KB Ok
4 Correct 10 ms 9968 KB Ok
5 Correct 11 ms 9968 KB Ok
6 Correct 10 ms 9968 KB Ok
7 Correct 9 ms 10116 KB Ok
8 Correct 10 ms 10116 KB Ok
9 Correct 10 ms 10116 KB Ok
10 Correct 10 ms 10116 KB Ok
11 Correct 12 ms 10116 KB Ok
12 Correct 9 ms 10116 KB Ok
13 Correct 9 ms 10116 KB Ok
14 Correct 9 ms 10116 KB Ok
15 Correct 9 ms 10116 KB Ok
16 Correct 9 ms 10116 KB Ok
17 Correct 9 ms 10116 KB Ok
18 Correct 16 ms 10116 KB Ok
19 Correct 47 ms 10748 KB Ok
20 Correct 30 ms 10748 KB Ok
21 Correct 50 ms 10892 KB Ok
22 Correct 38 ms 10892 KB Ok
23 Correct 10 ms 10892 KB Ok
24 Correct 10 ms 10892 KB Ok
25 Correct 10 ms 10892 KB Ok
26 Correct 10 ms 10892 KB Ok
27 Correct 12 ms 10892 KB Ok
28 Correct 11 ms 10892 KB Ok
29 Correct 11 ms 10892 KB Ok
30 Correct 10 ms 10892 KB Ok
31 Correct 9 ms 10892 KB Ok
32 Correct 9 ms 10892 KB Ok
33 Correct 10 ms 10892 KB Ok
34 Correct 19 ms 23240 KB Ok
35 Correct 17 ms 23240 KB Ok
36 Correct 15 ms 23240 KB Ok
37 Correct 15 ms 23240 KB Ok
38 Correct 14 ms 23240 KB Ok
39 Correct 16 ms 23240 KB Ok
40 Correct 14 ms 23240 KB Ok
41 Correct 15 ms 23240 KB Ok
42 Correct 16 ms 23240 KB Ok
43 Correct 15 ms 23240 KB Ok
44 Correct 23 ms 23240 KB Ok
45 Correct 25 ms 23240 KB Ok
46 Correct 25 ms 23240 KB Ok
47 Correct 27 ms 23240 KB Ok
48 Correct 23 ms 23240 KB Ok
49 Correct 22 ms 23240 KB Ok
50 Correct 25 ms 23240 KB Ok
51 Correct 22 ms 23240 KB Ok
52 Correct 24 ms 23240 KB Ok
53 Correct 23 ms 23240 KB Ok
54 Correct 314 ms 23240 KB Ok
55 Correct 402 ms 23240 KB Ok
56 Correct 381 ms 23240 KB Ok
57 Correct 298 ms 23240 KB Ok
58 Correct 340 ms 23240 KB Ok
59 Correct 330 ms 23240 KB Ok
60 Correct 309 ms 23240 KB Ok
61 Correct 302 ms 23240 KB Ok
62 Correct 409 ms 23240 KB Ok
63 Correct 334 ms 23240 KB Ok
64 Correct 430 ms 23240 KB Ok
65 Correct 372 ms 23240 KB Ok
66 Correct 341 ms 23240 KB Ok
67 Correct 273 ms 23240 KB Ok
68 Correct 331 ms 23240 KB Ok
69 Correct 897 ms 23240 KB Ok
70 Correct 884 ms 23240 KB Ok
71 Correct 673 ms 23240 KB Ok
72 Correct 809 ms 23240 KB Ok
73 Correct 753 ms 23240 KB Ok
74 Correct 654 ms 23240 KB Ok
75 Correct 693 ms 23240 KB Ok
76 Correct 861 ms 23240 KB Ok
77 Correct 733 ms 23240 KB Ok
78 Correct 873 ms 23240 KB Ok
79 Correct 791 ms 23240 KB Ok
80 Correct 738 ms 23240 KB Ok
81 Correct 778 ms 23240 KB Ok
82 Correct 705 ms 23240 KB Ok
83 Correct 797 ms 23240 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Ok
2 Correct 10 ms 9880 KB Ok
3 Correct 9 ms 9880 KB Ok
4 Correct 10 ms 9968 KB Ok
5 Correct 11 ms 9968 KB Ok
6 Correct 10 ms 9968 KB Ok
7 Correct 9 ms 10116 KB Ok
8 Correct 10 ms 10116 KB Ok
9 Correct 10 ms 10116 KB Ok
10 Correct 10 ms 10116 KB Ok
11 Correct 12 ms 10116 KB Ok
12 Correct 9 ms 10116 KB Ok
13 Correct 9 ms 10116 KB Ok
14 Correct 9 ms 10116 KB Ok
15 Correct 9 ms 10116 KB Ok
16 Correct 9 ms 10116 KB Ok
17 Correct 9 ms 10116 KB Ok
18 Correct 16 ms 10116 KB Ok
19 Correct 47 ms 10748 KB Ok
20 Correct 30 ms 10748 KB Ok
21 Correct 50 ms 10892 KB Ok
22 Correct 38 ms 10892 KB Ok
23 Correct 10 ms 10892 KB Ok
24 Correct 10 ms 10892 KB Ok
25 Correct 10 ms 10892 KB Ok
26 Correct 10 ms 10892 KB Ok
27 Correct 12 ms 10892 KB Ok
28 Correct 11 ms 10892 KB Ok
29 Correct 11 ms 10892 KB Ok
30 Correct 10 ms 10892 KB Ok
31 Correct 9 ms 10892 KB Ok
32 Correct 9 ms 10892 KB Ok
33 Correct 10 ms 10892 KB Ok
34 Correct 10 ms 10892 KB Ok
35 Correct 9 ms 10892 KB Ok
36 Correct 12 ms 10892 KB Ok
37 Correct 10 ms 10892 KB Ok
38 Correct 10 ms 10892 KB Ok
39 Correct 467 ms 20312 KB Ok
40 Correct 425 ms 20932 KB Ok
41 Correct 940 ms 23240 KB Ok
42 Correct 607 ms 23240 KB Ok
43 Correct 367 ms 23240 KB Ok
44 Correct 606 ms 23240 KB Ok
45 Correct 19 ms 23240 KB Ok
46 Correct 17 ms 23240 KB Ok
47 Correct 15 ms 23240 KB Ok
48 Correct 15 ms 23240 KB Ok
49 Correct 14 ms 23240 KB Ok
50 Correct 16 ms 23240 KB Ok
51 Correct 14 ms 23240 KB Ok
52 Correct 15 ms 23240 KB Ok
53 Correct 16 ms 23240 KB Ok
54 Correct 15 ms 23240 KB Ok
55 Correct 23 ms 23240 KB Ok
56 Correct 25 ms 23240 KB Ok
57 Correct 25 ms 23240 KB Ok
58 Correct 27 ms 23240 KB Ok
59 Correct 23 ms 23240 KB Ok
60 Correct 22 ms 23240 KB Ok
61 Correct 25 ms 23240 KB Ok
62 Correct 22 ms 23240 KB Ok
63 Correct 24 ms 23240 KB Ok
64 Correct 23 ms 23240 KB Ok
65 Correct 314 ms 23240 KB Ok
66 Correct 402 ms 23240 KB Ok
67 Correct 381 ms 23240 KB Ok
68 Correct 298 ms 23240 KB Ok
69 Correct 340 ms 23240 KB Ok
70 Correct 330 ms 23240 KB Ok
71 Correct 309 ms 23240 KB Ok
72 Correct 302 ms 23240 KB Ok
73 Correct 409 ms 23240 KB Ok
74 Correct 334 ms 23240 KB Ok
75 Correct 430 ms 23240 KB Ok
76 Correct 372 ms 23240 KB Ok
77 Correct 341 ms 23240 KB Ok
78 Correct 273 ms 23240 KB Ok
79 Correct 331 ms 23240 KB Ok
80 Correct 897 ms 23240 KB Ok
81 Correct 884 ms 23240 KB Ok
82 Correct 673 ms 23240 KB Ok
83 Correct 809 ms 23240 KB Ok
84 Correct 753 ms 23240 KB Ok
85 Correct 654 ms 23240 KB Ok
86 Correct 693 ms 23240 KB Ok
87 Correct 861 ms 23240 KB Ok
88 Correct 733 ms 23240 KB Ok
89 Correct 873 ms 23240 KB Ok
90 Correct 791 ms 23240 KB Ok
91 Correct 738 ms 23240 KB Ok
92 Correct 778 ms 23240 KB Ok
93 Correct 705 ms 23240 KB Ok
94 Correct 797 ms 23240 KB Ok
95 Correct 897 ms 24788 KB Ok
96 Correct 1470 ms 31716 KB Ok
97 Correct 1396 ms 31716 KB Ok
98 Correct 962 ms 31716 KB Ok
99 Correct 1153 ms 31716 KB Ok
100 Correct 1179 ms 31716 KB Ok
101 Correct 1355 ms 31716 KB Ok
102 Correct 1322 ms 31716 KB Ok
103 Correct 1268 ms 31716 KB Ok
104 Correct 1549 ms 31716 KB Ok
105 Correct 1528 ms 31716 KB Ok
106 Correct 1173 ms 31716 KB Ok
107 Correct 1382 ms 31716 KB Ok
108 Correct 1554 ms 31716 KB Ok
109 Correct 1198 ms 31896 KB Ok
110 Execution timed out 2074 ms 34120 KB Time limit exceeded
111 Halted 0 ms 0 KB -