oj.uz

Submission #887409

# Submission time Handle Problem Language Result Execution time Memory
887409 2023-12-14T12:56:28 Z pcc Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 39336 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 4e5+10;
int n,m;
vector<int> paths[mxn];
int deg[mxn];
queue<int> q;
int arr[mxn];

bool check(int tar){
	for(int i = 0;i+n<=tar;i++){
		paths[i+n].push_back(i);
		deg[i]++;
	}
	for(int i = 0;i+m<=tar;i++){
		paths[i].push_back(i+m);
		deg[i+m]++;
	}
	for(int i = 0;i<=tar;i++){
		if(!deg[i])q.push(i);
	}
	int p = 0;
	while(!q.empty()){
		auto now = q.front();
		arr[now] = ++p;
		q.pop();
		for(auto nxt:paths[now]){
			deg[nxt]--;
			if(!deg[nxt])q.push(nxt);
		}
	}
	for(int i = 0;i<=tar;i++){
		paths[i].clear();
		deg[i] = 0;
	}
	//cout<<tar<<":"<<p<<endl;
	return p == tar+1;
}

void solve(){
	cin>>n>>m;
	int l = 0,r = max(n,m)*2;
	while(l != r){
		int mid = (l+r+1)>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}
	check(l);
	cout<<l<<'\n';
	//for(int i = 1;i<=l;i++)cout<<arr[i]<<' ';cout<<endl;
	for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
	return;
}

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

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:59:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |  for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
      |  ^~~
sequence.cpp:59:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |  for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
      |                                                    ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12772 KB Ok
4 Correct 2 ms 12636 KB Ok
5 Correct 2 ms 12636 KB Ok
6 Correct 5 ms 12892 KB Ok
7 Correct 18 ms 13460 KB Ok
8 Correct 9 ms 13064 KB Ok
9 Correct 20 ms 13660 KB Ok
10 Correct 13 ms 13148 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12732 KB Ok
4 Correct 3 ms 12636 KB Ok
5 Correct 2 ms 12636 KB Ok
6 Correct 188 ms 21128 KB Ok
7 Correct 174 ms 21380 KB Ok
8 Correct 344 ms 23296 KB Ok
9 Correct 228 ms 23052 KB Ok
10 Correct 148 ms 18204 KB Ok
11 Correct 230 ms 22672 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12636 KB Ok
4 Correct 2 ms 12636 KB Ok
5 Correct 2 ms 12636 KB Ok
6 Correct 3 ms 12632 KB Ok
7 Correct 2 ms 12636 KB Ok
8 Correct 2 ms 12740 KB Ok
9 Correct 2 ms 12636 KB Ok
10 Correct 2 ms 12636 KB Ok
11 Correct 3 ms 12632 KB Ok
12 Correct 2 ms 12636 KB Ok
13 Correct 3 ms 12636 KB Ok
14 Correct 2 ms 12808 KB Ok
15 Correct 2 ms 12636 KB Ok
16 Correct 2 ms 12636 KB Ok
17 Correct 3 ms 12632 KB Ok
18 Correct 3 ms 12636 KB Ok
19 Correct 3 ms 12636 KB Ok
20 Correct 3 ms 12632 KB Ok
21 Correct 3 ms 12632 KB Ok
22 Correct 2 ms 12636 KB Ok
23 Correct 2 ms 12636 KB Ok
24 Correct 5 ms 12892 KB Ok
25 Correct 5 ms 12956 KB Ok
26 Correct 5 ms 12892 KB Ok
27 Correct 6 ms 12892 KB Ok
28 Correct 4 ms 12892 KB Ok
29 Correct 5 ms 12928 KB Ok
30 Correct 5 ms 12892 KB Ok
31 Correct 5 ms 12888 KB Ok
32 Correct 5 ms 12892 KB Ok
33 Correct 5 ms 12936 KB Ok
34 Correct 8 ms 12888 KB Ok
35 Correct 8 ms 13088 KB Ok
36 Correct 8 ms 12892 KB Ok
37 Correct 9 ms 12892 KB Ok
38 Correct 8 ms 12892 KB Ok
39 Correct 7 ms 12888 KB Ok
40 Correct 8 ms 12892 KB Ok
41 Correct 8 ms 12888 KB Ok
42 Correct 8 ms 12888 KB Ok
43 Correct 8 ms 12992 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12636 KB Ok
4 Correct 2 ms 12636 KB Ok
5 Correct 2 ms 12636 KB Ok
6 Correct 3 ms 12632 KB Ok
7 Correct 2 ms 12636 KB Ok
8 Correct 2 ms 12740 KB Ok
9 Correct 2 ms 12636 KB Ok
10 Correct 2 ms 12636 KB Ok
11 Correct 3 ms 12632 KB Ok
12 Correct 2 ms 12636 KB Ok
13 Correct 2 ms 12636 KB Ok
14 Correct 2 ms 12636 KB Ok
15 Correct 2 ms 12772 KB Ok
16 Correct 2 ms 12636 KB Ok
17 Correct 2 ms 12636 KB Ok
18 Correct 5 ms 12892 KB Ok
19 Correct 18 ms 13460 KB Ok
20 Correct 9 ms 13064 KB Ok
21 Correct 20 ms 13660 KB Ok
22 Correct 13 ms 13148 KB Ok
23 Correct 3 ms 12636 KB Ok
24 Correct 2 ms 12808 KB Ok
25 Correct 2 ms 12636 KB Ok
26 Correct 2 ms 12636 KB Ok
27 Correct 3 ms 12632 KB Ok
28 Correct 3 ms 12636 KB Ok
29 Correct 3 ms 12636 KB Ok
30 Correct 3 ms 12632 KB Ok
31 Correct 3 ms 12632 KB Ok
32 Correct 2 ms 12636 KB Ok
33 Correct 2 ms 12636 KB Ok
34 Correct 5 ms 12892 KB Ok
35 Correct 5 ms 12956 KB Ok
36 Correct 5 ms 12892 KB Ok
37 Correct 6 ms 12892 KB Ok
38 Correct 4 ms 12892 KB Ok
39 Correct 5 ms 12928 KB Ok
40 Correct 5 ms 12892 KB Ok
41 Correct 5 ms 12888 KB Ok
42 Correct 5 ms 12892 KB Ok
43 Correct 5 ms 12936 KB Ok
44 Correct 8 ms 12888 KB Ok
45 Correct 8 ms 13088 KB Ok
46 Correct 8 ms 12892 KB Ok
47 Correct 9 ms 12892 KB Ok
48 Correct 8 ms 12892 KB Ok
49 Correct 7 ms 12888 KB Ok
50 Correct 8 ms 12892 KB Ok
51 Correct 8 ms 12888 KB Ok
52 Correct 8 ms 12888 KB Ok
53 Correct 8 ms 12992 KB Ok
54 Correct 135 ms 17188 KB Ok
55 Correct 155 ms 17584 KB Ok
56 Correct 149 ms 17464 KB Ok
57 Correct 115 ms 16924 KB Ok
58 Correct 136 ms 17376 KB Ok
59 Correct 133 ms 17232 KB Ok
60 Correct 117 ms 16912 KB Ok
61 Correct 117 ms 17068 KB Ok
62 Correct 163 ms 17488 KB Ok
63 Correct 121 ms 17152 KB Ok
64 Correct 164 ms 17408 KB Ok
65 Correct 141 ms 17388 KB Ok
66 Correct 131 ms 17244 KB Ok
67 Correct 109 ms 16964 KB Ok
68 Correct 135 ms 17624 KB Ok
69 Correct 273 ms 21540 KB Ok
70 Correct 275 ms 22712 KB Ok
71 Correct 250 ms 20792 KB Ok
72 Correct 268 ms 21840 KB Ok
73 Correct 255 ms 21328 KB Ok
74 Correct 234 ms 20336 KB Ok
75 Correct 248 ms 20620 KB Ok
76 Correct 294 ms 22516 KB Ok
77 Correct 230 ms 19772 KB Ok
78 Correct 270 ms 22164 KB Ok
79 Correct 262 ms 21516 KB Ok
80 Correct 263 ms 21396 KB Ok
81 Correct 264 ms 21812 KB Ok
82 Correct 269 ms 21516 KB Ok
83 Correct 241 ms 20276 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Ok
2 Correct 2 ms 12636 KB Ok
3 Correct 2 ms 12636 KB Ok
4 Correct 2 ms 12636 KB Ok
5 Correct 2 ms 12636 KB Ok
6 Correct 3 ms 12632 KB Ok
7 Correct 2 ms 12636 KB Ok
8 Correct 2 ms 12740 KB Ok
9 Correct 2 ms 12636 KB Ok
10 Correct 2 ms 12636 KB Ok
11 Correct 3 ms 12632 KB Ok
12 Correct 2 ms 12636 KB Ok
13 Correct 2 ms 12636 KB Ok
14 Correct 2 ms 12636 KB Ok
15 Correct 2 ms 12772 KB Ok
16 Correct 2 ms 12636 KB Ok
17 Correct 2 ms 12636 KB Ok
18 Correct 5 ms 12892 KB Ok
19 Correct 18 ms 13460 KB Ok
20 Correct 9 ms 13064 KB Ok
21 Correct 20 ms 13660 KB Ok
22 Correct 13 ms 13148 KB Ok
23 Correct 3 ms 12636 KB Ok
24 Correct 2 ms 12808 KB Ok
25 Correct 2 ms 12636 KB Ok
26 Correct 2 ms 12636 KB Ok
27 Correct 3 ms 12632 KB Ok
28 Correct 3 ms 12636 KB Ok
29 Correct 3 ms 12636 KB Ok
30 Correct 3 ms 12632 KB Ok
31 Correct 3 ms 12632 KB Ok
32 Correct 2 ms 12636 KB Ok
33 Correct 2 ms 12636 KB Ok
34 Correct 2 ms 12636 KB Ok
35 Correct 2 ms 12636 KB Ok
36 Correct 2 ms 12732 KB Ok
37 Correct 3 ms 12636 KB Ok
38 Correct 2 ms 12636 KB Ok
39 Correct 188 ms 21128 KB Ok
40 Correct 174 ms 21380 KB Ok
41 Correct 344 ms 23296 KB Ok
42 Correct 228 ms 23052 KB Ok
43 Correct 148 ms 18204 KB Ok
44 Correct 230 ms 22672 KB Ok
45 Correct 5 ms 12892 KB Ok
46 Correct 5 ms 12956 KB Ok
47 Correct 5 ms 12892 KB Ok
48 Correct 6 ms 12892 KB Ok
49 Correct 4 ms 12892 KB Ok
50 Correct 5 ms 12928 KB Ok
51 Correct 5 ms 12892 KB Ok
52 Correct 5 ms 12888 KB Ok
53 Correct 5 ms 12892 KB Ok
54 Correct 5 ms 12936 KB Ok
55 Correct 8 ms 12888 KB Ok
56 Correct 8 ms 13088 KB Ok
57 Correct 8 ms 12892 KB Ok
58 Correct 9 ms 12892 KB Ok
59 Correct 8 ms 12892 KB Ok
60 Correct 7 ms 12888 KB Ok
61 Correct 8 ms 12892 KB Ok
62 Correct 8 ms 12888 KB Ok
63 Correct 8 ms 12888 KB Ok
64 Correct 8 ms 12992 KB Ok
65 Correct 135 ms 17188 KB Ok
66 Correct 155 ms 17584 KB Ok
67 Correct 149 ms 17464 KB Ok
68 Correct 115 ms 16924 KB Ok
69 Correct 136 ms 17376 KB Ok
70 Correct 133 ms 17232 KB Ok
71 Correct 117 ms 16912 KB Ok
72 Correct 117 ms 17068 KB Ok
73 Correct 163 ms 17488 KB Ok
74 Correct 121 ms 17152 KB Ok
75 Correct 164 ms 17408 KB Ok
76 Correct 141 ms 17388 KB Ok
77 Correct 131 ms 17244 KB Ok
78 Correct 109 ms 16964 KB Ok
79 Correct 135 ms 17624 KB Ok
80 Correct 273 ms 21540 KB Ok
81 Correct 275 ms 22712 KB Ok
82 Correct 250 ms 20792 KB Ok
83 Correct 268 ms 21840 KB Ok
84 Correct 255 ms 21328 KB Ok
85 Correct 234 ms 20336 KB Ok
86 Correct 248 ms 20620 KB Ok
87 Correct 294 ms 22516 KB Ok
88 Correct 230 ms 19772 KB Ok
89 Correct 270 ms 22164 KB Ok
90 Correct 262 ms 21516 KB Ok
91 Correct 263 ms 21396 KB Ok
92 Correct 264 ms 21812 KB Ok
93 Correct 269 ms 21516 KB Ok
94 Correct 241 ms 20276 KB Ok
95 Correct 346 ms 24560 KB Ok
96 Correct 550 ms 30232 KB Ok
97 Correct 548 ms 27500 KB Ok
98 Correct 394 ms 28404 KB Ok
99 Correct 503 ms 26328 KB Ok
100 Correct 500 ms 26796 KB Ok
101 Correct 502 ms 28132 KB Ok
102 Correct 469 ms 27036 KB Ok
103 Correct 478 ms 28180 KB Ok
104 Correct 581 ms 29656 KB Ok
105 Correct 562 ms 29260 KB Ok
106 Correct 440 ms 29400 KB Ok
107 Correct 515 ms 28692 KB Ok
108 Correct 586 ms 29428 KB Ok
109 Correct 519 ms 30192 KB Ok
110 Execution timed out 2045 ms 39336 KB Time limit exceeded
111 Halted 0 ms 0 KB -