oj.uz

Submission #65821

# Submission time Handle Problem Language Result Execution time Memory
65821 2018-08-09T00:50:00 Z kingpig9 Nice sequence (IZhO18_sequence) C++11
58 / 100
 2000 ms 24876 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 4e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, M;
vector<int> adj[MAXN];
vector<int> topo;
int indeg[MAXN];

bool moo (int g) {
	topo.clear();
	//x -> x + M or x + N -> x

	for (int x = 0; x <= g; x++) {
		indeg[x] = 0;
		adj[x].clear();
	}

	for (int x = 0; x + M <= g; x++) {
		adj[x].push_back(x + M);
		indeg[x + M]++;
	}
	for (int x = 0; x + N <= g; x++) {
		adj[x + N].push_back(x);
		indeg[x]++;
	}

	stack<int> stk;
	for (int x = 0; x <= g; x++) {
		if (indeg[x] == 0) {
			stk.push(x);
		}
	}

	while (!stk.empty()) {
		int x = stk.top();
		stk.pop();
		topo.push_back(x);
		for (int y : adj[x]) {
			if (--indeg[y] == 0) {
				stk.push(y);
			}
		}
	}

	for (int x = 0; x <= g; x++) {
		if (indeg[x]) {
			return false;
		}
	}
	return true;
}

vector<int> go() {
	int lo = min(N, M) - 1, hi = N + M;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (moo(mid)) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	moo(lo);

	vector<int> ans(lo + 1);
	int ind0 = find(all(topo), 0) - topo.begin();
	for (int i = 0; i <= lo; i++) {
		ans[topo[i]] = i - ind0;
	}
	for (int i = lo; i >= 1; i--) {
		ans[i] -= ans[i - 1];
	}
	ans.erase(ans.begin());
	return ans;
}

int main() {
	int nq;
	scanf("%d", &nq);
	for (int qi = 1; qi <= nq; qi++) {
		scanf("%d %d", &N, &M);
		vector<int> ans = go();
		printf("%lu\n", ans.size());
		for (int x : ans) {
			printf("%d ", x);
		}
		puts("");
	}
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &nq);
  ~~~~~^~~~~~~~~~~
sequence.cpp:92: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 13 ms 9848 KB Ok
2 Correct 12 ms 9848 KB Ok
3 Correct 12 ms 9876 KB Ok
4 Correct 12 ms 10008 KB Ok
5 Correct 11 ms 10124 KB Ok
6 Correct 12 ms 10232 KB Ok
7 Correct 12 ms 10232 KB Ok
8 Correct 13 ms 10232 KB Ok
9 Correct 12 ms 10232 KB Ok
10 Correct 10 ms 10232 KB Ok
11 Correct 12 ms 10232 KB Ok
12 Correct 14 ms 10232 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Ok
2 Correct 13 ms 10232 KB Ok
3 Correct 11 ms 10232 KB Ok
4 Correct 11 ms 10232 KB Ok
5 Correct 11 ms 10232 KB Ok
6 Correct 24 ms 10484 KB Ok
7 Correct 48 ms 11116 KB Ok
8 Correct 28 ms 11116 KB Ok
9 Correct 56 ms 11312 KB Ok
10 Correct 34 ms 11312 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11312 KB Ok
2 Correct 12 ms 11312 KB Ok
3 Correct 12 ms 11312 KB Ok
4 Correct 12 ms 11312 KB Ok
5 Correct 11 ms 11312 KB Ok
6 Correct 544 ms 21652 KB Ok
7 Correct 552 ms 21652 KB Ok
8 Correct 867 ms 24876 KB Ok
9 Correct 690 ms 24876 KB Ok
10 Correct 393 ms 24876 KB Ok
11 Correct 787 ms 24876 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9848 KB Ok
2 Correct 12 ms 9848 KB Ok
3 Correct 12 ms 9876 KB Ok
4 Correct 12 ms 10008 KB Ok
5 Correct 11 ms 10124 KB Ok
6 Correct 12 ms 10232 KB Ok
7 Correct 12 ms 10232 KB Ok
8 Correct 13 ms 10232 KB Ok
9 Correct 12 ms 10232 KB Ok
10 Correct 10 ms 10232 KB Ok
11 Correct 12 ms 10232 KB Ok
12 Correct 14 ms 10232 KB Ok
13 Correct 11 ms 10232 KB Ok
14 Correct 13 ms 10232 KB Ok
15 Correct 11 ms 10232 KB Ok
16 Correct 11 ms 10232 KB Ok
17 Correct 11 ms 10232 KB Ok
18 Correct 24 ms 10484 KB Ok
19 Correct 48 ms 11116 KB Ok
20 Correct 28 ms 11116 KB Ok
21 Correct 56 ms 11312 KB Ok
22 Correct 34 ms 11312 KB Ok
23 Correct 11 ms 11312 KB Ok
24 Correct 12 ms 11312 KB Ok
25 Correct 12 ms 11312 KB Ok
26 Correct 13 ms 11312 KB Ok
27 Correct 12 ms 11312 KB Ok
28 Correct 12 ms 11312 KB Ok
29 Correct 11 ms 11312 KB Ok
30 Correct 13 ms 11312 KB Ok
31 Correct 12 ms 11312 KB Ok
32 Correct 13 ms 11312 KB Ok
33 Correct 12 ms 11312 KB Ok
34 Correct 19 ms 24876 KB Ok
35 Correct 18 ms 24876 KB Ok
36 Correct 19 ms 24876 KB Ok
37 Correct 18 ms 24876 KB Ok
38 Correct 16 ms 24876 KB Ok
39 Correct 15 ms 24876 KB Ok
40 Correct 17 ms 24876 KB Ok
41 Correct 18 ms 24876 KB Ok
42 Correct 18 ms 24876 KB Ok
43 Correct 16 ms 24876 KB Ok
44 Correct 26 ms 24876 KB Ok
45 Correct 31 ms 24876 KB Ok
46 Correct 26 ms 24876 KB Ok
47 Correct 27 ms 24876 KB Ok
48 Correct 27 ms 24876 KB Ok
49 Correct 30 ms 24876 KB Ok
50 Correct 29 ms 24876 KB Ok
51 Correct 25 ms 24876 KB Ok
52 Correct 27 ms 24876 KB Ok
53 Correct 27 ms 24876 KB Ok
54 Correct 735 ms 24876 KB Ok
55 Correct 1006 ms 24876 KB Ok
56 Correct 862 ms 24876 KB Ok
57 Correct 390 ms 24876 KB Ok
58 Correct 774 ms 24876 KB Ok
59 Correct 596 ms 24876 KB Ok
60 Correct 445 ms 24876 KB Ok
61 Correct 410 ms 24876 KB Ok
62 Correct 965 ms 24876 KB Ok
63 Correct 564 ms 24876 KB Ok
64 Correct 976 ms 24876 KB Ok
65 Correct 703 ms 24876 KB Ok
66 Correct 518 ms 24876 KB Ok
67 Correct 530 ms 24876 KB Ok
68 Correct 506 ms 24876 KB Ok
69 Execution timed out 2075 ms 24876 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9848 KB Ok
2 Correct 12 ms 9848 KB Ok
3 Correct 12 ms 9876 KB Ok
4 Correct 12 ms 10008 KB Ok
5 Correct 11 ms 10124 KB Ok
6 Correct 12 ms 10232 KB Ok
7 Correct 12 ms 10232 KB Ok
8 Correct 13 ms 10232 KB Ok
9 Correct 12 ms 10232 KB Ok
10 Correct 10 ms 10232 KB Ok
11 Correct 12 ms 10232 KB Ok
12 Correct 14 ms 10232 KB Ok
13 Correct 11 ms 10232 KB Ok
14 Correct 13 ms 10232 KB Ok
15 Correct 11 ms 10232 KB Ok
16 Correct 11 ms 10232 KB Ok
17 Correct 11 ms 10232 KB Ok
18 Correct 24 ms 10484 KB Ok
19 Correct 48 ms 11116 KB Ok
20 Correct 28 ms 11116 KB Ok
21 Correct 56 ms 11312 KB Ok
22 Correct 34 ms 11312 KB Ok
23 Correct 11 ms 11312 KB Ok
24 Correct 12 ms 11312 KB Ok
25 Correct 12 ms 11312 KB Ok
26 Correct 13 ms 11312 KB Ok
27 Correct 12 ms 11312 KB Ok
28 Correct 12 ms 11312 KB Ok
29 Correct 11 ms 11312 KB Ok
30 Correct 13 ms 11312 KB Ok
31 Correct 12 ms 11312 KB Ok
32 Correct 13 ms 11312 KB Ok
33 Correct 12 ms 11312 KB Ok
34 Correct 12 ms 11312 KB Ok
35 Correct 12 ms 11312 KB Ok
36 Correct 12 ms 11312 KB Ok
37 Correct 12 ms 11312 KB Ok
38 Correct 11 ms 11312 KB Ok
39 Correct 544 ms 21652 KB Ok
40 Correct 552 ms 21652 KB Ok
41 Correct 867 ms 24876 KB Ok
42 Correct 690 ms 24876 KB Ok
43 Correct 393 ms 24876 KB Ok
44 Correct 787 ms 24876 KB Ok
45 Correct 19 ms 24876 KB Ok
46 Correct 18 ms 24876 KB Ok
47 Correct 19 ms 24876 KB Ok
48 Correct 18 ms 24876 KB Ok
49 Correct 16 ms 24876 KB Ok
50 Correct 15 ms 24876 KB Ok
51 Correct 17 ms 24876 KB Ok
52 Correct 18 ms 24876 KB Ok
53 Correct 18 ms 24876 KB Ok
54 Correct 16 ms 24876 KB Ok
55 Correct 26 ms 24876 KB Ok
56 Correct 31 ms 24876 KB Ok
57 Correct 26 ms 24876 KB Ok
58 Correct 27 ms 24876 KB Ok
59 Correct 27 ms 24876 KB Ok
60 Correct 30 ms 24876 KB Ok
61 Correct 29 ms 24876 KB Ok
62 Correct 25 ms 24876 KB Ok
63 Correct 27 ms 24876 KB Ok
64 Correct 27 ms 24876 KB Ok
65 Correct 735 ms 24876 KB Ok
66 Correct 1006 ms 24876 KB Ok
67 Correct 862 ms 24876 KB Ok
68 Correct 390 ms 24876 KB Ok
69 Correct 774 ms 24876 KB Ok
70 Correct 596 ms 24876 KB Ok
71 Correct 445 ms 24876 KB Ok
72 Correct 410 ms 24876 KB Ok
73 Correct 965 ms 24876 KB Ok
74 Correct 564 ms 24876 KB Ok
75 Correct 976 ms 24876 KB Ok
76 Correct 703 ms 24876 KB Ok
77 Correct 518 ms 24876 KB Ok
78 Correct 530 ms 24876 KB Ok
79 Correct 506 ms 24876 KB Ok
80 Execution timed out 2075 ms 24876 KB Time limit exceeded
81 Halted 0 ms 0 KB -