QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115124#124. Libraryminhcool19 46ms14720kbC++172.1kb2023-06-24 17:10:562023-06-24 17:10:58

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 17:10:58]
  • Judged
  • Verdict: 19
  • Time: 46ms
  • Memory: 14720kb
  • [2023-06-24 17:10:56]
  • Submitted

answer

//#define local
#ifndef local
#include "library.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

vector<int> Adj[N];

int ans[1005][1005];

int n;

#ifdef local
int Query(vector<int> v){
	cout << "? ";
	for(auto it : v) cout << it << " ";
	cout << "\n";
	int x;
	cin >> x;
	return x;
}

void Answer(vector<int> v){
	cout << "! ";
	for(auto it : v) cout << it << " ";
	cout << "\n";
	exit(0);
}
#endif

int cal(int i2, int le, int ri){
//	if(ans[le][ri]) return ans[le][ri];
	//cout << i2 << " " << le << " " << ri << "\n";
    if(le > ri) return 1;
	vector<int> v(n);
    for(int i = 0; i < n; i++) v[i] = 0;
	v[i2 - 1] = 1;
	for(int i = le - 1; i <= ri - 1; i++) v[i] = 1;
	return ans[le][ri] = Query(v);
}

bool vis[N];
vector<int> arr;

void dfs(int u, int p){
	arr.pb(u);	
	for(auto v : Adj[u]) if(v != p) dfs(v, u);
}

void Solve(int N){
	n = N;
	for(int i = 1; i < n; i++){
		int lst = i;
		while(Adj[i].size() < 2){	
			int le = lst + 1, ri = n;
			if(le > ri) break;
			if(cal(i, lst + 1, ri) > cal(lst + 1, lst + 1, ri)) break;
			while(le < ri){
				int mid = (le + ri) >> 1;
				if(cal(i, lst + 1, mid) > cal(lst + 1, lst + 1, mid)) le = mid + 1;
				else ri = mid;
			}
			//cout << "OKAY " << i << " " << le << "\n";
			Adj[i].pb(le);
			Adj[le].pb(i);
			lst = le;
		}
	}
	int st = -1;
	for(int i = 1; i <= n; i++) if(Adj[i].size() <= 1) st = i;
	dfs(st, st);
	Answer(arr);
}

#ifdef local
void process(){
	int n;
	cin >> n;
	int x;
	for(int i = 0; i < n; i++) cin >> x;
	Solve(n);
}

signed main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	process();
}
#endif

詳細信息

Subtask #1:

score: 19
Accepted

Test #1:

score: 19
Accepted
time: 5ms
memory: 11876kb

input:

192
17
6
145
10
132
34
129
8
137
157
65
54
138
85
60
190
52
75
179
23
167
41
117
186
165
26
111
73
49
92
3
81
96
11
152
45
56
33
182
15
130
166
105
19
158
159
156
149
169
153
106
134
114
148
124
80
28
68
184
62
104
67
150
128
175
116
144
183
189
151
173
39
108
71
79
5
47
99
162
163
177
69
20
136
82
...

output:

Accepted : 2930

result:

ok 

Test #2:

score: 0
Accepted
time: 5ms
memory: 11572kb

input:

191
69
178
96
53
32
141
87
158
154
29
44
164
113
17
81
75
147
166
124
50
184
142
48
98
168
66
60
130
151
55
30
133
19
175
177
138
25
149
110
12
119
108
173
71
136
172
150
39
117
13
144
40
91
70
102
121
186
191
24
157
185
2
86
163
131
99
135
65
22
174
139
115
106
23
125
20
34
82
90
77
182
132
85
9
18...

output:

Accepted : 2906

result:

ok 

Test #3:

score: 0
Accepted
time: 1ms
memory: 11652kb

input:

200
142
34
69
26
136
143
176
140
115
181
3
41
79
178
10
153
121
42
118
177
65
120
148
165
103
55
188
23
112
196
144
9
168
73
117
149
89
157
108
123
93
47
70
48
91
107
56
146
180
38
193
13
85
164
129
101
80
92
109
124
77
156
81
175
63
49
189
116
102
169
52
200
161
199
170
64
174
198
135
183
151
90
35...

output:

Accepted : 3072

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 12272kb

input:

200
91
162
140
77
52
56
37
65
50
147
106
57
193
121
103
47
83
119
185
126
76
154
166
163
123
63
129
6
48
114
49
178
45
136
132
53
177
80
171
197
68
122
19
130
26
192
150
149
108
196
72
1
188
172
66
191
93
3
142
18
170
12
42
15
187
25
75
20
28
131
59
101
23
115
181
10
51
70
153
40
39
195
46
127
120
2...

output:

Accepted : 3074

result:

ok 

Test #5:

score: 0
Accepted
time: 5ms
memory: 11848kb

input:

200
6
107
47
4
119
28
33
189
181
129
138
27
93
136
43
63
124
112
162
75
81
30
149
150
131
186
17
7
139
178
133
123
32
46
160
199
184
67
193
90
130
164
98
92
156
72
104
77
110
65
135
29
68
159
3
195
196
180
49
102
190
66
37
185
147
99
200
1
176
57
152
70
191
167
76
11
58
144
161
169
126
84
122
105
9
...

output:

Accepted : 3076

result:

ok 

Test #6:

score: 0
Accepted
time: 5ms
memory: 11776kb

input:

200
119
131
73
170
89
113
103
5
72
178
91
85
64
12
166
138
175
82
136
147
96
75
127
11
61
78
184
111
80
172
181
139
81
191
199
180
124
20
135
13
68
44
130
176
120
36
48
162
188
29
54
41
98
45
58
158
126
183
182
84
66
51
117
55
28
42
187
50
69
122
114
70
23
194
174
186
167
100
155
128
27
107
3
74
47
...

output:

Accepted : 3108

result:

ok 

Test #7:

score: 0
Accepted
time: 2ms
memory: 11488kb

input:

200
62
181
22
131
103
47
11
87
197
61
63
17
116
199
172
117
95
193
161
147
101
80
156
187
34
24
132
75
29
160
71
112
138
174
102
65
139
31
52
55
60
82
42
91
77
200
48
93
108
106
128
150
6
115
144
45
163
149
107
119
177
173
3
167
74
86
114
13
189
100
179
176
169
194
162
18
68
14
25
148
69
94
164
57
1...

output:

Accepted : 3074

result:

ok 

Test #8:

score: 0
Accepted
time: 0ms
memory: 12436kb

input:

193
67
133
62
43
184
187
123
9
103
34
102
143
119
42
12
150
25
70
45
35
110
113
76
177
139
149
118
130
168
186
64
58
82
39
141
178
53
138
182
131
56
52
140
60
188
72
111
114
162
112
95
109
10
3
84
108
47
15
134
81
122
74
156
1
100
50
5
27
171
175
94
166
193
160
46
18
116
38
172
121
181
144
98
127
15...

output:

Accepted : 2954

result:

ok 

Test #9:

score: 0
Accepted
time: 1ms
memory: 14720kb

input:

199
166
45
85
139
135
30
65
2
36
159
143
5
76
16
146
82
156
20
154
31
195
193
35
192
165
48
41
118
56
109
173
70
91
132
68
1
131
121
134
100
119
97
79
46
164
12
43
15
64
71
176
190
188
158
27
88
124
7
177
87
187
25
75
98
21
114
194
24
130
145
23
198
66
110
175
152
34
115
19
53
58
162
149
57
49
163
5...

output:

Accepted : 3036

result:

ok 

Test #10:

score: 0
Accepted
time: 4ms
memory: 14640kb

input:

129
34
75
74
78
64
110
38
6
35
100
76
126
87
102
90
71
52
127
108
7
104
37
97
72
25
116
66
8
92
91
26
99
4
12
18
48
56
81
69
3
105
70
20
51
44
83
62
21
123
19
86
28
50
84
32
77
46
80
24
115
41
89
27
33
1
9
93
120
40
107
49
39
98
2
119
118
122
14
55
16
113
109
124
54
73
47
85
15
101
42
45
57
128
65
6...

output:

Accepted : 1828

result:

ok 

Test #11:

score: 0
Accepted
time: 2ms
memory: 12336kb

input:

1
1

output:

Accepted : 0

result:

ok 

Test #12:

score: 0
Accepted
time: 0ms
memory: 11408kb

input:

2
2
1

output:

Accepted : 2

result:

ok 

Test #13:

score: 0
Accepted
time: 1ms
memory: 12192kb

input:

3
2
1
3

output:

Accepted : 8

result:

ok 

Test #14:

score: 0
Accepted
time: 3ms
memory: 11580kb

input:

4
4
2
3
1

output:

Accepted : 14

result:

ok 

Test #15:

score: 0
Accepted
time: 4ms
memory: 14708kb

input:

15
6
14
3
4
8
2
7
5
11
13
10
15
12
9
1

output:

Accepted : 112

result:

ok 

Test #16:

score: 0
Accepted
time: 3ms
memory: 11252kb

input:

27
22
16
19
13
4
26
1
15
17
24
6
25
12
27
2
7
10
21
20
8
11
23
3
5
14
18
9

output:

Accepted : 258

result:

ok 

Subtask #2:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 46ms
memory: 14608kb

input:

1000
972
265
212
27
724
465
50
304
37
134
246
257
177
482
90
974
616
221
151
912
946
366
590
277
187
976
394
765
643
740
385
665
749
585
923
92
920
994
48
405
978
893
477
381
788
992
825
680
785
297
679
116
836
31
333
714
828
922
492
890
919
237
188
677
557
522
867
368
19
690
29
632
832
17
107
485
3...

output:

Wrong Answer [3]

result:

wrong answer