oj.uz

Submission #948739

# Submission time Handle Problem Language Result Execution time Memory
948739 2024-03-18T12:52:39 Z willychan Nice sequence (IZhO18_sequence) C++17
100 / 100
 310 ms 35412 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int N = 5e5;
int P[N];
int cnt[N];
int query(int a){
	if(P[a]==a) return a;
	P[a] = query(P[a]);
	return P[a];
}
void solve(){
	int n,m;cin>>n>>m;
	swap(n,m);
	/*
	if(n==1 && m==1){
		cout<<0<<"\n";
		return;
	}
	*/
	int i=0;
	for(;i<N;i++){
		P[i]=i;
		cnt[i]=0;
		if(i-m>=0){
			if(query(i)==query(i-m)){
				break;	
			}
			P[query(i)]=query(i-m);
			cnt[i]++;
		}
		if(i-n>=0){
			if(query(i)==query(i-n)){
				break;	
			}
			P[query(i)]=query(i-n);
			cnt[i-n]++;
		}
	}
	vector<int> ord;
	queue<int> q;
	for(int j=0;j<i;j++){
		if(cnt[j]==0) q.push(j);
	}
	while(q.size())	{
		int cur = q.front();
		q.pop();
		ord.push_back(cur);
		if(cur-n>=0){
			cnt[cur-n]--;
			if(cnt[cur-n]==0) q.push(cur-n);
		}
		if(cur+m<i){
			cnt[cur+m]--;
			if(cnt[cur+m]==0) q.push(cur+m);
		}
	}
	vector<int> ans(i);
	for(int j=0;j<i;j++) ans[ord[j]]=i-j;
	cout<<i-1<<"\n";
	for(int j=1;j<i;j++) cout<<ans[j]-ans[j-1]<<" ";
	cout<<"\n";
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}

	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 2 ms 2648 KB Ok
7 Correct 6 ms 2908 KB Ok
8 Correct 3 ms 2652 KB Ok
9 Correct 7 ms 2908 KB Ok
10 Correct 4 ms 2652 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 0 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 55 ms 7132 KB Ok
7 Correct 48 ms 7492 KB Ok
8 Correct 90 ms 10348 KB Ok
9 Correct 69 ms 10504 KB Ok
10 Correct 40 ms 5776 KB Ok
11 Correct 73 ms 8824 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2476 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2396 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2392 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 0 ms 2396 KB Ok
17 Correct 1 ms 2392 KB Ok
18 Correct 1 ms 2396 KB Ok
19 Correct 1 ms 2396 KB Ok
20 Correct 1 ms 2396 KB Ok
21 Correct 1 ms 2396 KB Ok
22 Correct 0 ms 2396 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 2 ms 2392 KB Ok
25 Correct 2 ms 2396 KB Ok
26 Correct 2 ms 2396 KB Ok
27 Correct 2 ms 2396 KB Ok
28 Correct 1 ms 2560 KB Ok
29 Correct 2 ms 2396 KB Ok
30 Correct 1 ms 2396 KB Ok
31 Correct 2 ms 2604 KB Ok
32 Correct 2 ms 2396 KB Ok
33 Correct 2 ms 2392 KB Ok
34 Correct 3 ms 2648 KB Ok
35 Correct 3 ms 2648 KB Ok
36 Correct 3 ms 2652 KB Ok
37 Correct 3 ms 2648 KB Ok
38 Correct 3 ms 2652 KB Ok
39 Correct 3 ms 2652 KB Ok
40 Correct 3 ms 2648 KB Ok
41 Correct 3 ms 2648 KB Ok
42 Correct 3 ms 2648 KB Ok
43 Correct 3 ms 2652 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2476 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2396 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2392 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 0 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 1 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 2 ms 2648 KB Ok
19 Correct 6 ms 2908 KB Ok
20 Correct 3 ms 2652 KB Ok
21 Correct 7 ms 2908 KB Ok
22 Correct 4 ms 2652 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 1 ms 2396 KB Ok
25 Correct 1 ms 2396 KB Ok
26 Correct 0 ms 2396 KB Ok
27 Correct 1 ms 2392 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 1 ms 2396 KB Ok
30 Correct 1 ms 2396 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 0 ms 2396 KB Ok
33 Correct 1 ms 2396 KB Ok
34 Correct 2 ms 2392 KB Ok
35 Correct 2 ms 2396 KB Ok
36 Correct 2 ms 2396 KB Ok
37 Correct 2 ms 2396 KB Ok
38 Correct 1 ms 2560 KB Ok
39 Correct 2 ms 2396 KB Ok
40 Correct 1 ms 2396 KB Ok
41 Correct 2 ms 2604 KB Ok
42 Correct 2 ms 2396 KB Ok
43 Correct 2 ms 2392 KB Ok
44 Correct 3 ms 2648 KB Ok
45 Correct 3 ms 2648 KB Ok
46 Correct 3 ms 2652 KB Ok
47 Correct 3 ms 2648 KB Ok
48 Correct 3 ms 2652 KB Ok
49 Correct 3 ms 2652 KB Ok
50 Correct 3 ms 2648 KB Ok
51 Correct 3 ms 2648 KB Ok
52 Correct 3 ms 2648 KB Ok
53 Correct 3 ms 2652 KB Ok
54 Correct 41 ms 5636 KB Ok
55 Correct 48 ms 5792 KB Ok
56 Correct 54 ms 6056 KB Ok
57 Correct 36 ms 5252 KB Ok
58 Correct 42 ms 5600 KB Ok
59 Correct 42 ms 5388 KB Ok
60 Correct 36 ms 5436 KB Ok
61 Correct 37 ms 5328 KB Ok
62 Correct 49 ms 5752 KB Ok
63 Correct 41 ms 5508 KB Ok
64 Correct 46 ms 5908 KB Ok
65 Correct 44 ms 5740 KB Ok
66 Correct 40 ms 5532 KB Ok
67 Correct 35 ms 5316 KB Ok
68 Correct 41 ms 5428 KB Ok
69 Correct 71 ms 9200 KB Ok
70 Correct 76 ms 10276 KB Ok
71 Correct 71 ms 8480 KB Ok
72 Correct 72 ms 9756 KB Ok
73 Correct 69 ms 9020 KB Ok
74 Correct 69 ms 8304 KB Ok
75 Correct 68 ms 8316 KB Ok
76 Correct 74 ms 9868 KB Ok
77 Correct 67 ms 7792 KB Ok
78 Correct 75 ms 9596 KB Ok
79 Correct 71 ms 9212 KB Ok
80 Correct 75 ms 9136 KB Ok
81 Correct 71 ms 9572 KB Ok
82 Correct 71 ms 9096 KB Ok
83 Correct 67 ms 8204 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2476 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2396 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2392 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 0 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 1 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 2 ms 2648 KB Ok
19 Correct 6 ms 2908 KB Ok
20 Correct 3 ms 2652 KB Ok
21 Correct 7 ms 2908 KB Ok
22 Correct 4 ms 2652 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 1 ms 2396 KB Ok
25 Correct 1 ms 2396 KB Ok
26 Correct 0 ms 2396 KB Ok
27 Correct 1 ms 2392 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 1 ms 2396 KB Ok
30 Correct 1 ms 2396 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 0 ms 2396 KB Ok
33 Correct 1 ms 2396 KB Ok
34 Correct 1 ms 2396 KB Ok
35 Correct 0 ms 2396 KB Ok
36 Correct 1 ms 2396 KB Ok
37 Correct 1 ms 2396 KB Ok
38 Correct 1 ms 2396 KB Ok
39 Correct 55 ms 7132 KB Ok
40 Correct 48 ms 7492 KB Ok
41 Correct 90 ms 10348 KB Ok
42 Correct 69 ms 10504 KB Ok
43 Correct 40 ms 5776 KB Ok
44 Correct 73 ms 8824 KB Ok
45 Correct 2 ms 2392 KB Ok
46 Correct 2 ms 2396 KB Ok
47 Correct 2 ms 2396 KB Ok
48 Correct 2 ms 2396 KB Ok
49 Correct 1 ms 2560 KB Ok
50 Correct 2 ms 2396 KB Ok
51 Correct 1 ms 2396 KB Ok
52 Correct 2 ms 2604 KB Ok
53 Correct 2 ms 2396 KB Ok
54 Correct 2 ms 2392 KB Ok
55 Correct 3 ms 2648 KB Ok
56 Correct 3 ms 2648 KB Ok
57 Correct 3 ms 2652 KB Ok
58 Correct 3 ms 2648 KB Ok
59 Correct 3 ms 2652 KB Ok
60 Correct 3 ms 2652 KB Ok
61 Correct 3 ms 2648 KB Ok
62 Correct 3 ms 2648 KB Ok
63 Correct 3 ms 2648 KB Ok
64 Correct 3 ms 2652 KB Ok
65 Correct 41 ms 5636 KB Ok
66 Correct 48 ms 5792 KB Ok
67 Correct 54 ms 6056 KB Ok
68 Correct 36 ms 5252 KB Ok
69 Correct 42 ms 5600 KB Ok
70 Correct 42 ms 5388 KB Ok
71 Correct 36 ms 5436 KB Ok
72 Correct 37 ms 5328 KB Ok
73 Correct 49 ms 5752 KB Ok
74 Correct 41 ms 5508 KB Ok
75 Correct 46 ms 5908 KB Ok
76 Correct 44 ms 5740 KB Ok
77 Correct 40 ms 5532 KB Ok
78 Correct 35 ms 5316 KB Ok
79 Correct 41 ms 5428 KB Ok
80 Correct 71 ms 9200 KB Ok
81 Correct 76 ms 10276 KB Ok
82 Correct 71 ms 8480 KB Ok
83 Correct 72 ms 9756 KB Ok
84 Correct 69 ms 9020 KB Ok
85 Correct 69 ms 8304 KB Ok
86 Correct 68 ms 8316 KB Ok
87 Correct 74 ms 9868 KB Ok
88 Correct 67 ms 7792 KB Ok
89 Correct 75 ms 9596 KB Ok
90 Correct 71 ms 9212 KB Ok
91 Correct 75 ms 9136 KB Ok
92 Correct 71 ms 9572 KB Ok
93 Correct 71 ms 9096 KB Ok
94 Correct 67 ms 8204 KB Ok
95 Correct 101 ms 10656 KB Ok
96 Correct 145 ms 14092 KB Ok
97 Correct 220 ms 12648 KB Ok
98 Correct 108 ms 11408 KB Ok
99 Correct 128 ms 13216 KB Ok
100 Correct 130 ms 12004 KB Ok
101 Correct 133 ms 13848 KB Ok
102 Correct 130 ms 13272 KB Ok
103 Correct 124 ms 12256 KB Ok
104 Correct 151 ms 13840 KB Ok
105 Correct 150 ms 14232 KB Ok
106 Correct 119 ms 13424 KB Ok
107 Correct 150 ms 14196 KB Ok
108 Correct 151 ms 14388 KB Ok
109 Correct 135 ms 13916 KB Ok
110 Correct 293 ms 27408 KB Ok
111 Correct 308 ms 35412 KB Ok
112 Correct 285 ms 29208 KB Ok
113 Correct 295 ms 32284 KB Ok
114 Correct 297 ms 33896 KB Ok
115 Correct 310 ms 32756 KB Ok
116 Correct 290 ms 32724 KB Ok
117 Correct 304 ms 33656 KB Ok
118 Correct 293 ms 29980 KB Ok
119 Correct 298 ms 34056 KB Ok
120 Correct 285 ms 29956 KB Ok
121 Correct 278 ms 29000 KB Ok
122 Correct 287 ms 31428 KB Ok
123 Correct 298 ms 35384 KB Ok
124 Correct 285 ms 26488 KB Ok
125 Correct 275 ms 20056 KB Ok