QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91915#5091. 大冬天题SenseAnone100 ✓199ms155980kbC++142.3kb2023-03-29 21:43:442023-03-29 21:43:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 21:43:45]
  • 评测
  • 测评结果:100
  • 用时:199ms
  • 内存:155980kb
  • [2023-03-29 21:43:44]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int Edgecnt,head[8000005],To[8000005],nxt[8000005],W[8000005];
void AddEdge(int a,int b,int c)
{
//	cerr<<a<<" "<<b<<" "<<c<<endl;
	To[Edgecnt]=b; nxt[Edgecnt]=head[a]; W[Edgecnt]=c; head[a]=Edgecnt++;
	To[Edgecnt]=a; nxt[Edgecnt]=head[b]; W[Edgecnt]=0; head[b]=Edgecnt++;
}
int S,T,cur[8000005],dis[8000005];
bool BFS()
{
	for(int i=1;i<=T;i++) dis[i]=0;
	queue<int>Q;Q.push(S);cur[S]=head[S];dis[S]=1;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=head[u];~i;i=nxt[i])
		{
			int v=To[i];
			if(!W[i]||dis[v]) continue;
			dis[v]=dis[u]+1; cur[v]=head[v];
			if(v==T) return true;
			Q.push(v);
		}
	}
	return false;
}
int DFS(int u,int Lim)
{
	if(u==T) return Lim;
	int res=0;
	for(int i=cur[u];~i&&res<Lim;i=nxt[i])
	{
		int v=To[i]; cur[u]=i;
		if(!W[i]||dis[v]!=dis[u]+1) continue;
		int Tmp=DFS(v,min(Lim-res,W[i]));
		if(!Tmp) dis[v]=-1;
		else res+=Tmp,W[i]-=Tmp,W[i^1]+=Tmp;
	}
	return res;
}
int Dinic()
{
	int Tmp,res=0;
	while(BFS()) 
		while((Tmp=DFS(S,1e9))) res+=Tmp;
	return res;
}
int Ans[1000005];
int main() {
	memset(head,-1,sizeof(head));
	int n,k;
	read(n);read(k);//I don't care about n
	S=2*k+1; T=S+1; 
	for(int i=1;i<=2*k-1;i+=2)
	{
		AddEdge(S,(i+1)/2,1); AddEdge(k+(i+1)/2,T,1);
		for(int j=0;(1<<j)<=4*k-2;j++)
		{
			if((1<<j)-i<=0) continue;
			if((1<<j)-i>2*k-1) break;
			AddEdge((i+1)/2,k+((1<<j)-i+1)/2,1);
		}
	}
	int res=Dinic();
	printf("%d\n",res);
	for(int i=0;i<Edgecnt;i+=2)
	{
		int u=To[i^1],v=To[i],w=W[i];
		if(1<=u&&u<=k&&k+1<=v&&v<=2*k&&!w) Ans[u]=(v-k);
	}
	for(int i=1;i<=k;i++) printf("%d\n",Ans[i]);
	return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。
*/


詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 44748kb

input:

527901620 3

output:

3
1
3
2

result:

ok Accepted.

Test #2:

score: 5
Accepted
time: 2ms
memory: 45004kb

input:

423744200 1

output:

1
1

result:

ok Accepted.

Test #3:

score: 5
Accepted
time: 1ms
memory: 43436kb

input:

870873520 8

output:

8
8
7
6
5
4
3
2
1

result:

ok Accepted.

Test #4:

score: 5
Accepted
time: 1ms
memory: 44268kb

input:

796450080 10

output:

10
2
1
6
5
4
3
10
9
8
7

result:

ok Accepted.

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #5:

score: 5
Accepted
time: 11ms
memory: 45828kb

input:

691352244 2

output:

2
2
1

result:

ok Accepted.

Test #6:

score: 5
Accepted
time: 1ms
memory: 45932kb

input:

537735946 4

output:

4
4
3
2
1

result:

ok Accepted.

Test #7:

score: 5
Accepted
time: 1ms
memory: 45388kb

input:

964421466 6

output:

6
2
1
6
5
4
3

result:

ok Accepted.

Test #8:

score: 5
Accepted
time: 1ms
memory: 46952kb

input:

804640404 8

output:

8
8
7
6
5
4
3
2
1

result:

ok Accepted.

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #9:

score: 15
Accepted
time: 0ms
memory: 45572kb

input:

815904616 163

output:

163
1
3
2
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
35
34
33
32
31
30
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
163
162
161
160
159
158
15...

result:

ok Accepted.

Test #10:

score: 15
Accepted
time: 2ms
memory: 46800kb

input:

261467732 174

output:

174
2
1
14
13
12
11
10
9
8
7
6
5
4
3
18
17
16
15
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
174
173
172
171
170
169
168
167
166
165
164
163
162
161
160...

result:

ok Accepted.

Test #11:

score: 15
Accepted
time: 7ms
memory: 46436kb

input:

170135212 52

output:

52
4
3
2
1
12
11
10
9
8
7
6
5
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13

result:

ok Accepted.

Test #12:

score: 15
Accepted
time: 9ms
memory: 45420kb

input:

914972990 139

output:

139
1
3
2
5
4
11
10
9
8
7
6
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33...

result:

ok Accepted.

Subtask #4:

score: 10
Accepted

Dependency #3:

100%
Accepted

Test #13:

score: 10
Accepted
time: 0ms
memory: 46892kb

input:

303514006 1401

output:

1401
1
7
6
5
4
3
2
121
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
3...

result:

ok Accepted.

Test #14:

score: 10
Accepted
time: 1ms
memory: 46200kb

input:

651391026 1584

output:

1584
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
464
463
462
461
460
459
458
457
456
455
454
453
452
451
450
449
448
447
446
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
430
429
428
427
426
425
...

result:

ok Accepted.

Test #15:

score: 10
Accepted
time: 4ms
memory: 46012kb

input:

196126306 1766

output:

1766
2
1
6
5
4
3
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
230
229
228
227
226
225
224
223
222
221
220
219
218
217
216
215
214
213
212
211
210
209
208
207
206
205
204
203
202
201
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
17...

result:

ok Accepted.

Test #16:

score: 10
Accepted
time: 1ms
memory: 45796kb

input:

904263684 1948

output:

1948
4
3
2
1
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
194...

result:

ok Accepted.

Subtask #5:

score: 25
Accepted

Test #17:

score: 25
Accepted
time: 137ms
memory: 122028kb

input:

1434450 717225

output:

717225
1
7
6
5
4
3
2
9
8
23
22
21
20
19
18
17
16
15
14
13
12
11
10
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
425
424
423
422
421
420
419
418
417
416
4...

result:

ok Accepted.

Test #18:

score: 25
Accepted
time: 177ms
memory: 135372kb

input:

1666706 833353

output:

833353
1
7
6
5
4
3
2
9
8
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163...

result:

ok Accepted.

Test #19:

score: 25
Accepted
time: 165ms
memory: 141828kb

input:

1768146 884073

output:

884073
1
7
6
5
4
3
2
9
8
23
22
21
20
19
18
17
16
15
14
13
12
11
10
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30...

result:

ok Accepted.

Test #20:

score: 25
Accepted
time: 137ms
memory: 115852kb

input:

1333926 666963

output:

666963
1
3
2
13
12
11
10
9
8
7
6
5
4
19
18
17
16
15
14
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
173
172
171
170
169
168
167
166
165
164
163
162
161
1...

result:

ok Accepted.

Subtask #6:

score: 10
Accepted

Dependency #4:

100%
Accepted

Test #21:

score: 10
Accepted
time: 10ms
memory: 53828kb

input:

121768078 34399

output:

34399
1
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
33
32
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
417
416
415
414
41...

result:

ok Accepted.

Test #22:

score: 10
Accepted
time: 8ms
memory: 48788kb

input:

567903556 38581

output:

38581
1
3
2
5
4
11
10
9
8
7
6
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163
16...

result:

ok Accepted.

Test #23:

score: 10
Accepted
time: 7ms
memory: 49084kb

input:

414440938 42763

output:

42763
1
3
2
5
4
11
10
9
8
7
6
245
244
243
242
241
240
239
238
237
236
235
234
233
232
231
230
229
228
227
226
225
224
223
222
221
220
219
218
217
216
215
214
213
212
211
210
209
208
207
206
205
204
203
202
201
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
17...

result:

ok Accepted.

Test #24:

score: 10
Accepted
time: 12ms
memory: 51116kb

input:

310652458 46946

output:

46946
2
1
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
158
157
1...

result:

ok Accepted.

Subtask #7:

score: 15
Accepted

Dependency #6:

100%
Accepted

Test #25:

score: 15
Accepted
time: 197ms
memory: 153156kb

input:

385664412 991454

output:

991454
2
1
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
34
33
32
31
222
221
220
219
218
217
216
215
214
213
212
211
210
209
208
207
206
205
204
203
202
201
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
...

result:

ok Accepted.

Test #26:

score: 15
Accepted
time: 52ms
memory: 74820kb

input:

795580394 295636

output:

295636
4
3
2
1
12
11
10
9
8
7
6
5
20
19
18
17
16
15
14
13
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
212
211
210
209
208
207
206
205
204
203
202
201
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
17...

result:

ok Accepted.

Test #27:

score: 15
Accepted
time: 135ms
memory: 108372kb

input:

639325794 599818

output:

599818
2
1
6
5
4
3
10
9
8
7
246
245
244
243
242
241
240
239
238
237
236
235
234
233
232
231
230
229
228
227
226
225
224
223
222
221
220
219
218
217
216
215
214
213
212
211
210
209
208
207
206
205
204
203
202
201
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
...

result:

ok Accepted.

Test #28:

score: 15
Accepted
time: 163ms
memory: 147344kb

input:

514552014 904000

output:

904000
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
16...

result:

ok Accepted.

Subtask #8:

score: 15
Accepted

Dependency #5:

100%
Accepted

Dependency #7:

100%
Accepted

Test #29:

score: 15
Accepted
time: 20ms
memory: 60984kb

input:

4043938008620250853548463463670539178824136101118676039998249773600296234199890542107734673644890238 182956

output:

182956
4
3
2
1
12
11
10
9
8
7
6
5
20
19
18
17
16
15
14
13
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
172
171
170
169
168
167
166
165
164
163
162
161
16...

result:

ok Accepted.

Test #30:

score: 15
Accepted
time: 66ms
memory: 81552kb

input:

6809505726107869121835226914314324742765939751165985001014682212595145094113574992502730535886215434 358074

output:

358074
2
1
6
5
4
3
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
70
69
68
67
66
65
64
63
62
61
60
59
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
...

result:

ok Accepted.

Test #31:

score: 15
Accepted
time: 199ms
memory: 155980kb

input:

2263258607536236028437491678008 1000000

output:

1000000
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
448
447
446
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
430
429
428
427
426
425
424
423
422
4...

result:

ok Accepted.

Test #32:

score: 15
Accepted
time: 196ms
memory: 152852kb

input:

36212137720579776454999866846484 1000000

output:

1000000
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
448
447
446
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
430
429
428
427
426
425
424
423
422
4...

result:

ok Accepted.