oj.uz

Submission #963165

# Submission time Handle Problem Language Result Execution time Memory
963165 2024-04-14T15:59:55 Z starchan Nice sequence (IZhO18_sequence) C++17
100 / 100
 1567 ms 76928 KB 
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 4e5+2;
int dp[MX];
vector<int> adj[MX];
vector<bool> vis(MX);

int solve(int u)
{
	if(vis[u])
		return dp[u];
	dp[u] = 0;
	vis[u] = 1;
	for(int v: adj[u])
		dp[u] = max(dp[u], solve(v));
	return ++dp[u];
}

signed main()
{
	fast();
	int t;
	cin >> t;
	while(t--)
	{
		int n, m;
		cin >> n >> m;
		int p = m;
		int N = 0;
		while(true)
		{
			N = max(N, p);
			p%=n;
			if(p == 0)
				break;
			p+=m;
		}
		N--;
		for(int i = 0; i <= N; i++)
		{
			adj[i].clear();
			if((i+m) <= N)
				adj[i].pb(i+m);
			if((i-n) >= 0)
				adj[i].pb(i-n);
		}

		vis.assign(N+1, false);
		vector<array<int, 2>> vi;
		for(int i = 0; i <= N; i++)
			vi.pb({-solve(i), i});
		sort(vi.begin(), vi.end());
		vector<int> a(N+1);
		for(int i = 0; i <= N; i++)
			a[vi[i][1]] = i;
		for(int i = N; i >= 1; i--)
			a[i]-=a[i-1];
		cout << N << "\n";
		for(int i = 1; i <= N; i++)
			cout << a[i] << " ";
		cout << "\n";
	}
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Ok
2 Correct 2 ms 10844 KB Ok
3 Correct 2 ms 10844 KB Ok
4 Correct 2 ms 10844 KB Ok
5 Correct 2 ms 10840 KB Ok
6 Correct 4 ms 11100 KB Ok
7 Correct 12 ms 11884 KB Ok
8 Correct 6 ms 11368 KB Ok
9 Correct 13 ms 11996 KB Ok
10 Correct 8 ms 11356 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Ok
2 Correct 2 ms 11096 KB Ok
3 Correct 2 ms 10844 KB Ok
4 Correct 2 ms 10844 KB Ok
5 Correct 2 ms 10840 KB Ok
6 Correct 135 ms 27688 KB Ok
7 Correct 135 ms 28268 KB Ok
8 Correct 255 ms 31680 KB Ok
9 Correct 143 ms 28068 KB Ok
10 Correct 109 ms 22004 KB Ok
11 Correct 170 ms 33408 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Ok
2 Correct 3 ms 10840 KB Ok
3 Correct 2 ms 10844 KB Ok
4 Correct 3 ms 10852 KB Ok
5 Correct 3 ms 10844 KB Ok
6 Correct 2 ms 10844 KB Ok
7 Correct 2 ms 10844 KB Ok
8 Correct 3 ms 10948 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 3 ms 10844 KB Ok
12 Correct 2 ms 10844 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 2 ms 10844 KB Ok
15 Correct 2 ms 10840 KB Ok
16 Correct 2 ms 10840 KB Ok
17 Correct 3 ms 10844 KB Ok
18 Correct 2 ms 10844 KB Ok
19 Correct 3 ms 10840 KB Ok
20 Correct 2 ms 10840 KB Ok
21 Correct 2 ms 10840 KB Ok
22 Correct 2 ms 10840 KB Ok
23 Correct 2 ms 10844 KB Ok
24 Correct 4 ms 11100 KB Ok
25 Correct 5 ms 11108 KB Ok
26 Correct 4 ms 11296 KB Ok
27 Correct 4 ms 11100 KB Ok
28 Correct 4 ms 11100 KB Ok
29 Correct 4 ms 10844 KB Ok
30 Correct 4 ms 10844 KB Ok
31 Correct 4 ms 11100 KB Ok
32 Correct 5 ms 11100 KB Ok
33 Correct 4 ms 11100 KB Ok
34 Correct 7 ms 11100 KB Ok
35 Correct 7 ms 11356 KB Ok
36 Correct 7 ms 11356 KB Ok
37 Correct 7 ms 11248 KB Ok
38 Correct 7 ms 11356 KB Ok
39 Correct 7 ms 11100 KB Ok
40 Correct 7 ms 11356 KB Ok
41 Correct 7 ms 11356 KB Ok
42 Correct 7 ms 11356 KB Ok
43 Correct 8 ms 11356 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Ok
2 Correct 3 ms 10840 KB Ok
3 Correct 2 ms 10844 KB Ok
4 Correct 3 ms 10852 KB Ok
5 Correct 3 ms 10844 KB Ok
6 Correct 2 ms 10844 KB Ok
7 Correct 2 ms 10844 KB Ok
8 Correct 3 ms 10948 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 3 ms 10844 KB Ok
12 Correct 2 ms 10844 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 2 ms 10844 KB Ok
15 Correct 2 ms 10844 KB Ok
16 Correct 2 ms 10844 KB Ok
17 Correct 2 ms 10840 KB Ok
18 Correct 4 ms 11100 KB Ok
19 Correct 12 ms 11884 KB Ok
20 Correct 6 ms 11368 KB Ok
21 Correct 13 ms 11996 KB Ok
22 Correct 8 ms 11356 KB Ok
23 Correct 2 ms 10844 KB Ok
24 Correct 2 ms 10844 KB Ok
25 Correct 2 ms 10840 KB Ok
26 Correct 2 ms 10840 KB Ok
27 Correct 3 ms 10844 KB Ok
28 Correct 2 ms 10844 KB Ok
29 Correct 3 ms 10840 KB Ok
30 Correct 2 ms 10840 KB Ok
31 Correct 2 ms 10840 KB Ok
32 Correct 2 ms 10840 KB Ok
33 Correct 2 ms 10844 KB Ok
34 Correct 4 ms 11100 KB Ok
35 Correct 5 ms 11108 KB Ok
36 Correct 4 ms 11296 KB Ok
37 Correct 4 ms 11100 KB Ok
38 Correct 4 ms 11100 KB Ok
39 Correct 4 ms 10844 KB Ok
40 Correct 4 ms 10844 KB Ok
41 Correct 4 ms 11100 KB Ok
42 Correct 5 ms 11100 KB Ok
43 Correct 4 ms 11100 KB Ok
44 Correct 7 ms 11100 KB Ok
45 Correct 7 ms 11356 KB Ok
46 Correct 7 ms 11356 KB Ok
47 Correct 7 ms 11248 KB Ok
48 Correct 7 ms 11356 KB Ok
49 Correct 7 ms 11100 KB Ok
50 Correct 7 ms 11356 KB Ok
51 Correct 7 ms 11356 KB Ok
52 Correct 7 ms 11356 KB Ok
53 Correct 8 ms 11356 KB Ok
54 Correct 93 ms 16732 KB Ok
55 Correct 107 ms 16956 KB Ok
56 Correct 117 ms 16940 KB Ok
57 Correct 75 ms 16104 KB Ok
58 Correct 99 ms 16588 KB Ok
59 Correct 93 ms 16304 KB Ok
60 Correct 81 ms 16108 KB Ok
61 Correct 78 ms 16408 KB Ok
62 Correct 110 ms 16928 KB Ok
63 Correct 89 ms 16084 KB Ok
64 Correct 110 ms 16736 KB Ok
65 Correct 108 ms 16908 KB Ok
66 Correct 87 ms 16632 KB Ok
67 Correct 78 ms 16436 KB Ok
68 Correct 90 ms 16452 KB Ok
69 Correct 187 ms 25408 KB Ok
70 Correct 189 ms 26444 KB Ok
71 Correct 179 ms 22608 KB Ok
72 Correct 172 ms 26096 KB Ok
73 Correct 184 ms 23124 KB Ok
74 Correct 188 ms 23428 KB Ok
75 Correct 190 ms 24148 KB Ok
76 Correct 196 ms 26572 KB Ok
77 Correct 180 ms 22560 KB Ok
78 Correct 202 ms 26500 KB Ok
79 Correct 190 ms 24640 KB Ok
80 Correct 199 ms 23400 KB Ok
81 Correct 185 ms 25644 KB Ok
82 Correct 181 ms 24736 KB Ok
83 Correct 178 ms 24360 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Ok
2 Correct 3 ms 10840 KB Ok
3 Correct 2 ms 10844 KB Ok
4 Correct 3 ms 10852 KB Ok
5 Correct 3 ms 10844 KB Ok
6 Correct 2 ms 10844 KB Ok
7 Correct 2 ms 10844 KB Ok
8 Correct 3 ms 10948 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 3 ms 10844 KB Ok
12 Correct 2 ms 10844 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 2 ms 10844 KB Ok
15 Correct 2 ms 10844 KB Ok
16 Correct 2 ms 10844 KB Ok
17 Correct 2 ms 10840 KB Ok
18 Correct 4 ms 11100 KB Ok
19 Correct 12 ms 11884 KB Ok
20 Correct 6 ms 11368 KB Ok
21 Correct 13 ms 11996 KB Ok
22 Correct 8 ms 11356 KB Ok
23 Correct 2 ms 10844 KB Ok
24 Correct 2 ms 10844 KB Ok
25 Correct 2 ms 10840 KB Ok
26 Correct 2 ms 10840 KB Ok
27 Correct 3 ms 10844 KB Ok
28 Correct 2 ms 10844 KB Ok
29 Correct 3 ms 10840 KB Ok
30 Correct 2 ms 10840 KB Ok
31 Correct 2 ms 10840 KB Ok
32 Correct 2 ms 10840 KB Ok
33 Correct 2 ms 10844 KB Ok
34 Correct 2 ms 10844 KB Ok
35 Correct 2 ms 11096 KB Ok
36 Correct 2 ms 10844 KB Ok
37 Correct 2 ms 10844 KB Ok
38 Correct 2 ms 10840 KB Ok
39 Correct 135 ms 27688 KB Ok
40 Correct 135 ms 28268 KB Ok
41 Correct 255 ms 31680 KB Ok
42 Correct 143 ms 28068 KB Ok
43 Correct 109 ms 22004 KB Ok
44 Correct 170 ms 33408 KB Ok
45 Correct 4 ms 11100 KB Ok
46 Correct 5 ms 11108 KB Ok
47 Correct 4 ms 11296 KB Ok
48 Correct 4 ms 11100 KB Ok
49 Correct 4 ms 11100 KB Ok
50 Correct 4 ms 10844 KB Ok
51 Correct 4 ms 10844 KB Ok
52 Correct 4 ms 11100 KB Ok
53 Correct 5 ms 11100 KB Ok
54 Correct 4 ms 11100 KB Ok
55 Correct 7 ms 11100 KB Ok
56 Correct 7 ms 11356 KB Ok
57 Correct 7 ms 11356 KB Ok
58 Correct 7 ms 11248 KB Ok
59 Correct 7 ms 11356 KB Ok
60 Correct 7 ms 11100 KB Ok
61 Correct 7 ms 11356 KB Ok
62 Correct 7 ms 11356 KB Ok
63 Correct 7 ms 11356 KB Ok
64 Correct 8 ms 11356 KB Ok
65 Correct 93 ms 16732 KB Ok
66 Correct 107 ms 16956 KB Ok
67 Correct 117 ms 16940 KB Ok
68 Correct 75 ms 16104 KB Ok
69 Correct 99 ms 16588 KB Ok
70 Correct 93 ms 16304 KB Ok
71 Correct 81 ms 16108 KB Ok
72 Correct 78 ms 16408 KB Ok
73 Correct 110 ms 16928 KB Ok
74 Correct 89 ms 16084 KB Ok
75 Correct 110 ms 16736 KB Ok
76 Correct 108 ms 16908 KB Ok
77 Correct 87 ms 16632 KB Ok
78 Correct 78 ms 16436 KB Ok
79 Correct 90 ms 16452 KB Ok
80 Correct 187 ms 25408 KB Ok
81 Correct 189 ms 26444 KB Ok
82 Correct 179 ms 22608 KB Ok
83 Correct 172 ms 26096 KB Ok
84 Correct 184 ms 23124 KB Ok
85 Correct 188 ms 23428 KB Ok
86 Correct 190 ms 24148 KB Ok
87 Correct 196 ms 26572 KB Ok
88 Correct 180 ms 22560 KB Ok
89 Correct 202 ms 26500 KB Ok
90 Correct 190 ms 24640 KB Ok
91 Correct 199 ms 23400 KB Ok
92 Correct 185 ms 25644 KB Ok
93 Correct 181 ms 24736 KB Ok
94 Correct 178 ms 24360 KB Ok
95 Correct 230 ms 25388 KB Ok
96 Correct 363 ms 34048 KB Ok
97 Correct 342 ms 30380 KB Ok
98 Correct 228 ms 28596 KB Ok
99 Correct 301 ms 28248 KB Ok
100 Correct 337 ms 28444 KB Ok
101 Correct 301 ms 33004 KB Ok
102 Correct 313 ms 31296 KB Ok
103 Correct 317 ms 31536 KB Ok
104 Correct 384 ms 33196 KB Ok
105 Correct 394 ms 34208 KB Ok
106 Correct 289 ms 32712 KB Ok
107 Correct 342 ms 33804 KB Ok
108 Correct 393 ms 33372 KB Ok
109 Correct 331 ms 32384 KB Ok
110 Correct 1203 ms 67352 KB Ok
111 Correct 1384 ms 76928 KB Ok
112 Correct 1448 ms 61876 KB Ok
113 Correct 1223 ms 73156 KB Ok
114 Correct 1403 ms 65724 KB Ok
115 Correct 1567 ms 73328 KB Ok
116 Correct 1431 ms 71856 KB Ok
117 Correct 1317 ms 74936 KB Ok
118 Correct 1344 ms 60584 KB Ok
119 Correct 1341 ms 76636 KB Ok
120 Correct 1323 ms 70480 KB Ok
121 Correct 1346 ms 66664 KB Ok
122 Correct 1287 ms 72068 KB Ok
123 Correct 1410 ms 73260 KB Ok
124 Correct 1279 ms 58340 KB Ok
125 Correct 785 ms 60460 KB Ok