QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115105 | #124. Library | minhcool | 19 | 47ms | 14736kb | C++17 | 2.1kb | 2023-06-24 16:46:20 | 2023-06-24 16:46:24 |
Judging History
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(1){
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
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 19
Accepted
Test #1:
score: 19
Accepted
time: 2ms
memory: 14648kb
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 : 3304
result:
ok
Test #2:
score: 0
Accepted
time: 5ms
memory: 12628kb
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 : 3278
result:
ok
Test #3:
score: 0
Accepted
time: 5ms
memory: 11740kb
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 : 3462
result:
ok
Test #4:
score: 0
Accepted
time: 2ms
memory: 14656kb
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 : 3464
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 14736kb
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 : 3466
result:
ok
Test #6:
score: 0
Accepted
time: 5ms
memory: 11976kb
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 : 3498
result:
ok
Test #7:
score: 0
Accepted
time: 5ms
memory: 14652kb
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 : 3464
result:
ok
Test #8:
score: 0
Accepted
time: 4ms
memory: 12072kb
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 : 3330
result:
ok
Test #9:
score: 0
Accepted
time: 5ms
memory: 12556kb
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 : 3424
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 14632kb
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 : 2076
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 11608kb
input:
1 1
output:
Accepted : 0
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 12324kb
input:
2 2 1
output:
Accepted : 2
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 12884kb
input:
3 2 1 3
output:
Accepted : 8
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 11628kb
input:
4 4 2 3 1
output:
Accepted : 16
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 11616kb
input:
15 6 14 3 4 8 2 7 5 11 13 10 15 12 9 1
output:
Accepted : 132
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 11172kb
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 : 302
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 47ms
memory: 14544kb
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