oj.uz

Submission #963164

# Submission time Handle Problem Language Result Execution time Memory
963164 2024-04-14T15:59:05 Z starchan Nice sequence (IZhO18_sequence) C++17
34 / 100
 2000 ms 20108 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;
	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 4 ms 10944 KB Ok
2 Correct 3 ms 10844 KB Ok
3 Correct 3 ms 10844 KB Ok
4 Correct 3 ms 10844 KB Ok
5 Correct 3 ms 10948 KB Ok
6 Correct 3 ms 10844 KB Ok
7 Correct 3 ms 10840 KB Ok
8 Correct 3 ms 10844 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 2 ms 10844 KB Ok
12 Correct 3 ms 11096 KB Ok

Subtask #2
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 3 ms 10840 KB Ok
4 Correct 3 ms 10844 KB Ok
5 Correct 3 ms 10844 KB Ok
6 Correct 71 ms 11116 KB Ok
7 Correct 1707 ms 12104 KB Ok
8 Correct 373 ms 11348 KB Ok
9 Execution timed out 2017 ms 12080 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10948 KB Ok
2 Correct 2 ms 10840 KB Ok
3 Correct 3 ms 10844 KB Ok
4 Correct 3 ms 10840 KB Ok
5 Correct 3 ms 10844 KB Ok
6 Execution timed out 2053 ms 20108 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10944 KB Ok
2 Correct 3 ms 10844 KB Ok
3 Correct 3 ms 10844 KB Ok
4 Correct 3 ms 10844 KB Ok
5 Correct 3 ms 10948 KB Ok
6 Correct 3 ms 10844 KB Ok
7 Correct 3 ms 10840 KB Ok
8 Correct 3 ms 10844 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 2 ms 10844 KB Ok
12 Correct 3 ms 11096 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 3 ms 10868 KB Ok
15 Correct 3 ms 10844 KB Ok
16 Correct 3 ms 10844 KB Ok
17 Correct 3 ms 10852 KB Ok
18 Correct 3 ms 10944 KB Ok
19 Correct 3 ms 10844 KB Ok
20 Correct 3 ms 10944 KB Ok
21 Correct 3 ms 10840 KB Ok
22 Correct 3 ms 10844 KB Ok
23 Correct 2 ms 10844 KB Ok
24 Correct 4 ms 11100 KB Ok
25 Correct 8 ms 10948 KB Ok
26 Correct 6 ms 11100 KB Ok
27 Correct 8 ms 11100 KB Ok
28 Correct 5 ms 11112 KB Ok
29 Correct 15 ms 11088 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 6 ms 10952 KB Ok
34 Correct 290 ms 11228 KB Ok
35 Correct 579 ms 11428 KB Ok
36 Correct 415 ms 11220 KB Ok
37 Correct 646 ms 11436 KB Ok
38 Correct 591 ms 11356 KB Ok
39 Correct 298 ms 11700 KB Ok
40 Correct 557 ms 11280 KB Ok
41 Correct 625 ms 11344 KB Ok
42 Correct 384 ms 11596 KB Ok
43 Correct 595 ms 11456 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10944 KB Ok
2 Correct 3 ms 10844 KB Ok
3 Correct 3 ms 10844 KB Ok
4 Correct 3 ms 10844 KB Ok
5 Correct 3 ms 10948 KB Ok
6 Correct 3 ms 10844 KB Ok
7 Correct 3 ms 10840 KB Ok
8 Correct 3 ms 10844 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 2 ms 10844 KB Ok
12 Correct 3 ms 11096 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 2 ms 10844 KB Ok
15 Correct 3 ms 10840 KB Ok
16 Correct 3 ms 10844 KB Ok
17 Correct 3 ms 10844 KB Ok
18 Correct 71 ms 11116 KB Ok
19 Correct 1707 ms 12104 KB Ok
20 Correct 373 ms 11348 KB Ok
21 Execution timed out 2017 ms 12080 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10944 KB Ok
2 Correct 3 ms 10844 KB Ok
3 Correct 3 ms 10844 KB Ok
4 Correct 3 ms 10844 KB Ok
5 Correct 3 ms 10948 KB Ok
6 Correct 3 ms 10844 KB Ok
7 Correct 3 ms 10840 KB Ok
8 Correct 3 ms 10844 KB Ok
9 Correct 2 ms 10840 KB Ok
10 Correct 2 ms 10844 KB Ok
11 Correct 2 ms 10844 KB Ok
12 Correct 3 ms 11096 KB Ok
13 Correct 2 ms 10844 KB Ok
14 Correct 2 ms 10844 KB Ok
15 Correct 3 ms 10840 KB Ok
16 Correct 3 ms 10844 KB Ok
17 Correct 3 ms 10844 KB Ok
18 Correct 71 ms 11116 KB Ok
19 Correct 1707 ms 12104 KB Ok
20 Correct 373 ms 11348 KB Ok
21 Execution timed out 2017 ms 12080 KB Time limit exceeded
22 Halted 0 ms 0 KB -