oj.uz

Submission #46506

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

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:40:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(v.size() == size + 1) {
     ~~~~~~~~~^~~~~~~~~~~
sequence.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
sequence.cpp:50: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:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &test);
  ~~~~~^~~~~~~~~~~~~
sequence.cpp:78: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 6 ms 4984 KB Ok
2 Correct 6 ms 5096 KB Ok
3 Correct 6 ms 5208 KB Ok
4 Correct 5 ms 5320 KB Ok
5 Correct 5 ms 5360 KB Ok
6 Correct 5 ms 5360 KB Ok
7 Correct 6 ms 5476 KB Ok
8 Correct 5 ms 5476 KB Ok
9 Correct 5 ms 5476 KB Ok
10 Correct 6 ms 5476 KB Ok
11 Correct 5 ms 5476 KB Ok
12 Correct 5 ms 5476 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5476 KB Ok
2 Correct 6 ms 5476 KB Ok
3 Correct 6 ms 5476 KB Ok
4 Correct 5 ms 5476 KB Ok
5 Correct 7 ms 5476 KB Ok
6 Correct 12 ms 5540 KB Ok
7 Correct 42 ms 6280 KB Ok
8 Correct 21 ms 6280 KB Ok
9 Correct 49 ms 6368 KB Ok
10 Correct 29 ms 6368 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6368 KB Ok
2 Correct 5 ms 6368 KB Ok
3 Correct 5 ms 6368 KB Ok
4 Correct 5 ms 6368 KB Ok
5 Correct 6 ms 6368 KB Ok
6 Correct 459 ms 15928 KB Ok
7 Correct 453 ms 16416 KB Ok
8 Correct 878 ms 18896 KB Ok
9 Correct 615 ms 18896 KB Ok
10 Correct 342 ms 18896 KB Ok
11 Correct 599 ms 18896 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 5096 KB Ok
3 Correct 6 ms 5208 KB Ok
4 Correct 5 ms 5320 KB Ok
5 Correct 5 ms 5360 KB Ok
6 Correct 5 ms 5360 KB Ok
7 Correct 6 ms 5476 KB Ok
8 Correct 5 ms 5476 KB Ok
9 Correct 5 ms 5476 KB Ok
10 Correct 6 ms 5476 KB Ok
11 Correct 5 ms 5476 KB Ok
12 Correct 5 ms 5476 KB Ok
13 Correct 6 ms 6368 KB Ok
14 Correct 5 ms 6368 KB Ok
15 Correct 6 ms 6368 KB Ok
16 Correct 6 ms 6368 KB Ok
17 Correct 6 ms 6368 KB Ok
18 Correct 6 ms 6368 KB Ok
19 Correct 5 ms 6368 KB Ok
20 Correct 6 ms 6368 KB Ok
21 Correct 6 ms 6368 KB Ok
22 Correct 6 ms 6368 KB Ok
23 Correct 6 ms 6368 KB Ok
24 Correct 12 ms 18896 KB Ok
25 Correct 12 ms 18896 KB Ok
26 Correct 11 ms 18896 KB Ok
27 Correct 11 ms 18896 KB Ok
28 Correct 10 ms 18896 KB Ok
29 Correct 10 ms 18896 KB Ok
30 Correct 11 ms 18896 KB Ok
31 Correct 17 ms 18896 KB Ok
32 Correct 12 ms 18896 KB Ok
33 Correct 11 ms 18896 KB Ok
34 Correct 18 ms 18896 KB Ok
35 Correct 19 ms 18896 KB Ok
36 Correct 20 ms 18896 KB Ok
37 Correct 20 ms 18896 KB Ok
38 Correct 19 ms 18896 KB Ok
39 Correct 18 ms 18896 KB Ok
40 Correct 21 ms 18896 KB Ok
41 Correct 19 ms 18896 KB Ok
42 Correct 21 ms 18896 KB Ok
43 Correct 21 ms 18896 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 5096 KB Ok
3 Correct 6 ms 5208 KB Ok
4 Correct 5 ms 5320 KB Ok
5 Correct 5 ms 5360 KB Ok
6 Correct 5 ms 5360 KB Ok
7 Correct 6 ms 5476 KB Ok
8 Correct 5 ms 5476 KB Ok
9 Correct 5 ms 5476 KB Ok
10 Correct 6 ms 5476 KB Ok
11 Correct 5 ms 5476 KB Ok
12 Correct 5 ms 5476 KB Ok
13 Correct 5 ms 5476 KB Ok
14 Correct 6 ms 5476 KB Ok
15 Correct 6 ms 5476 KB Ok
16 Correct 5 ms 5476 KB Ok
17 Correct 7 ms 5476 KB Ok
18 Correct 12 ms 5540 KB Ok
19 Correct 42 ms 6280 KB Ok
20 Correct 21 ms 6280 KB Ok
21 Correct 49 ms 6368 KB Ok
22 Correct 29 ms 6368 KB Ok
23 Correct 6 ms 6368 KB Ok
24 Correct 5 ms 6368 KB Ok
25 Correct 6 ms 6368 KB Ok
26 Correct 6 ms 6368 KB Ok
27 Correct 6 ms 6368 KB Ok
28 Correct 6 ms 6368 KB Ok
29 Correct 5 ms 6368 KB Ok
30 Correct 6 ms 6368 KB Ok
31 Correct 6 ms 6368 KB Ok
32 Correct 6 ms 6368 KB Ok
33 Correct 6 ms 6368 KB Ok
34 Correct 12 ms 18896 KB Ok
35 Correct 12 ms 18896 KB Ok
36 Correct 11 ms 18896 KB Ok
37 Correct 11 ms 18896 KB Ok
38 Correct 10 ms 18896 KB Ok
39 Correct 10 ms 18896 KB Ok
40 Correct 11 ms 18896 KB Ok
41 Correct 17 ms 18896 KB Ok
42 Correct 12 ms 18896 KB Ok
43 Correct 11 ms 18896 KB Ok
44 Correct 18 ms 18896 KB Ok
45 Correct 19 ms 18896 KB Ok
46 Correct 20 ms 18896 KB Ok
47 Correct 20 ms 18896 KB Ok
48 Correct 19 ms 18896 KB Ok
49 Correct 18 ms 18896 KB Ok
50 Correct 21 ms 18896 KB Ok
51 Correct 19 ms 18896 KB Ok
52 Correct 21 ms 18896 KB Ok
53 Correct 21 ms 18896 KB Ok
54 Correct 367 ms 18896 KB Ok
55 Correct 389 ms 18896 KB Ok
56 Correct 375 ms 18896 KB Ok
57 Correct 334 ms 18896 KB Ok
58 Correct 353 ms 18896 KB Ok
59 Correct 328 ms 18896 KB Ok
60 Correct 325 ms 18896 KB Ok
61 Correct 266 ms 18896 KB Ok
62 Correct 400 ms 18896 KB Ok
63 Correct 284 ms 18896 KB Ok
64 Correct 377 ms 18896 KB Ok
65 Correct 378 ms 18896 KB Ok
66 Correct 313 ms 18896 KB Ok
67 Correct 263 ms 18896 KB Ok
68 Correct 340 ms 18896 KB Ok
69 Correct 777 ms 18896 KB Ok
70 Correct 884 ms 18896 KB Ok
71 Correct 684 ms 18896 KB Ok
72 Correct 793 ms 18896 KB Ok
73 Correct 682 ms 18896 KB Ok
74 Correct 658 ms 18896 KB Ok
75 Correct 689 ms 18896 KB Ok
76 Correct 756 ms 18896 KB Ok
77 Correct 621 ms 18896 KB Ok
78 Correct 728 ms 18896 KB Ok
79 Correct 735 ms 18896 KB Ok
80 Correct 698 ms 18896 KB Ok
81 Correct 817 ms 18896 KB Ok
82 Correct 717 ms 18896 KB Ok
83 Correct 705 ms 18896 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Ok
2 Correct 6 ms 5096 KB Ok
3 Correct 6 ms 5208 KB Ok
4 Correct 5 ms 5320 KB Ok
5 Correct 5 ms 5360 KB Ok
6 Correct 5 ms 5360 KB Ok
7 Correct 6 ms 5476 KB Ok
8 Correct 5 ms 5476 KB Ok
9 Correct 5 ms 5476 KB Ok
10 Correct 6 ms 5476 KB Ok
11 Correct 5 ms 5476 KB Ok
12 Correct 5 ms 5476 KB Ok
13 Correct 5 ms 5476 KB Ok
14 Correct 6 ms 5476 KB Ok
15 Correct 6 ms 5476 KB Ok
16 Correct 5 ms 5476 KB Ok
17 Correct 7 ms 5476 KB Ok
18 Correct 12 ms 5540 KB Ok
19 Correct 42 ms 6280 KB Ok
20 Correct 21 ms 6280 KB Ok
21 Correct 49 ms 6368 KB Ok
22 Correct 29 ms 6368 KB Ok
23 Correct 6 ms 6368 KB Ok
24 Correct 5 ms 6368 KB Ok
25 Correct 6 ms 6368 KB Ok
26 Correct 6 ms 6368 KB Ok
27 Correct 6 ms 6368 KB Ok
28 Correct 6 ms 6368 KB Ok
29 Correct 5 ms 6368 KB Ok
30 Correct 6 ms 6368 KB Ok
31 Correct 6 ms 6368 KB Ok
32 Correct 6 ms 6368 KB Ok
33 Correct 6 ms 6368 KB Ok
34 Correct 6 ms 6368 KB Ok
35 Correct 5 ms 6368 KB Ok
36 Correct 5 ms 6368 KB Ok
37 Correct 5 ms 6368 KB Ok
38 Correct 6 ms 6368 KB Ok
39 Correct 459 ms 15928 KB Ok
40 Correct 453 ms 16416 KB Ok
41 Correct 878 ms 18896 KB Ok
42 Correct 615 ms 18896 KB Ok
43 Correct 342 ms 18896 KB Ok
44 Correct 599 ms 18896 KB Ok
45 Correct 12 ms 18896 KB Ok
46 Correct 12 ms 18896 KB Ok
47 Correct 11 ms 18896 KB Ok
48 Correct 11 ms 18896 KB Ok
49 Correct 10 ms 18896 KB Ok
50 Correct 10 ms 18896 KB Ok
51 Correct 11 ms 18896 KB Ok
52 Correct 17 ms 18896 KB Ok
53 Correct 12 ms 18896 KB Ok
54 Correct 11 ms 18896 KB Ok
55 Correct 18 ms 18896 KB Ok
56 Correct 19 ms 18896 KB Ok
57 Correct 20 ms 18896 KB Ok
58 Correct 20 ms 18896 KB Ok
59 Correct 19 ms 18896 KB Ok
60 Correct 18 ms 18896 KB Ok
61 Correct 21 ms 18896 KB Ok
62 Correct 19 ms 18896 KB Ok
63 Correct 21 ms 18896 KB Ok
64 Correct 21 ms 18896 KB Ok
65 Correct 367 ms 18896 KB Ok
66 Correct 389 ms 18896 KB Ok
67 Correct 375 ms 18896 KB Ok
68 Correct 334 ms 18896 KB Ok
69 Correct 353 ms 18896 KB Ok
70 Correct 328 ms 18896 KB Ok
71 Correct 325 ms 18896 KB Ok
72 Correct 266 ms 18896 KB Ok
73 Correct 400 ms 18896 KB Ok
74 Correct 284 ms 18896 KB Ok
75 Correct 377 ms 18896 KB Ok
76 Correct 378 ms 18896 KB Ok
77 Correct 313 ms 18896 KB Ok
78 Correct 263 ms 18896 KB Ok
79 Correct 340 ms 18896 KB Ok
80 Correct 777 ms 18896 KB Ok
81 Correct 884 ms 18896 KB Ok
82 Correct 684 ms 18896 KB Ok
83 Correct 793 ms 18896 KB Ok
84 Correct 682 ms 18896 KB Ok
85 Correct 658 ms 18896 KB Ok
86 Correct 689 ms 18896 KB Ok
87 Correct 756 ms 18896 KB Ok
88 Correct 621 ms 18896 KB Ok
89 Correct 728 ms 18896 KB Ok
90 Correct 735 ms 18896 KB Ok
91 Correct 698 ms 18896 KB Ok
92 Correct 817 ms 18896 KB Ok
93 Correct 717 ms 18896 KB Ok
94 Correct 705 ms 18896 KB Ok
95 Runtime error 357 ms 28080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Halted 0 ms 0 KB -