| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 630067 |
2022-08-15T15:38:45 Z |
Arnch |
Library (JOI18_library) |
C++17 |
|
222 ms |
4320 KB |
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
/*
Query(vector<int> &m);
Answer(vector<int> &res);
*/
#define Sz(x) (int)(x.size())
#define All(x) (x).begin(), (x).end()
const int N = 1e3 + 10;
bool mark[N], vis[N];
int e[N][N];
int Ask(vector<int> &ask) {
for(int i = 1; i <= Sz(ask); i++) ask[i - 1] = mark[i];
return Query(ask);
}
void Solve(int N) {
int n = N;
if(n == 1) {
vector<int> ans = {1};
Answer(ans);
return;
}
vector<vector<int> > vc;
vector<int> ask(N);
for(int i = 1; i <= n; i++) {
vc.push_back({i});
while(true) {
for(auto j : vc)
for(auto x : j) mark[x] = 1;
int t = Ask(ask);
if(t == Sz(vc)) break;
for(auto j : vc)
for(auto x : j) mark[x] = 0;
vector<int> res = vc.back(); vc.pop_back();
for(auto j : res) mark[j] = 1;
int l = 0, r = Sz(vc);
while(r - l > 1) {
int mid = (l + r) >> 1;
for(int i = l; i < mid; i++) {
for(auto j : vc[i]) mark[j] = 1;
}
t = Ask(ask);
for(int i = l; i < mid; i++) {
for(auto j : vc[i]) mark[j] = 0;
}
if(t != mid - l + 1) r = mid;
else l = mid;
}
for(auto j : res) mark[j] = 0;
int u1 = res[0], u2 = res.back();
int v1 = vc[l][0], v2 = vc[l].back();
/*cout<<"^**********" <<endl;
for(auto j : res) cout<<j <<' ';
cout<<endl;
for(auto j : vc[l]) cout<<j <<' ';
cout<<"**********" <<endl;*/
mark[u1] = mark[v1] = 1;
t = Ask(ask);
if(t == 1) {
e[u1][v1] = e[v1][u1] = 1;
mark[u1] = mark[v1] = 0;
reverse(All(vc[l]));
for(auto j : res) vc[l].push_back(j);
res.clear();
res = vc[l];
vc.erase(vc.begin() + l);
vc.push_back(res);
continue;
}
mark[u1] = mark[v1] = 0;
mark[u1] = mark[v2] = 1;
t = Ask(ask);
if(t == 1) {
e[u1][v2] = e[v2][u1] = 1;
mark[u1] = mark[v2] = 0;
for(auto j : res) vc[l].push_back(j);
res.clear();
res = vc[l];
vc.erase(vc.begin() + l);
vc.push_back(res);
continue;
}
mark[u1] = mark[v2] = 0;
mark[u2] = mark[v1] = 1;
t = Ask(ask);
if(t == 1) {
e[u2][v1] = e[v1][u2] = 1;
mark[u2] = mark[v1] = 0;
for(auto j : vc[l]) res.push_back(j);
vc[l].swap(res);
res.clear();
res = vc[l];
vc.erase(vc.begin() + l);
vc.push_back(res);
continue;
}
mark[u2] = mark[v1] = 0;
mark[u2] = mark[v2] = 1;
t = Ask(ask);
if(t == 1) {
e[u2][v2] = e[v2][u2] = 1;
mark[u2] = mark[v2] = 0;
reverse(All(res));
for(auto j : res) vc[l].push_back(j);
res.clear();
res = vc[l];
vc.erase(vc.begin() + l);
vc.push_back(res);
continue;
}
mark[u2] = mark[v2] = 0;
}
}
vector<int> res, ans;
int u;
for(int i = 1; i <= n; i++) {
int cnt = 0;
for(int j = 1; j <= n; j++) cnt += e[i][j];
if(cnt == 1) {
u = i;
vis[u] = 1;
break;
}
}
res.push_back(u);
while(!res.empty()) {
int u = res.back();
res.pop_back();
ans.push_back(u);
for(int j = 1; j <= n; j++) {
if(e[u][j] && !vis[j]) {
res.push_back(j);
vis[j] = 1;
break;
}
}
}
Answer(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
952 KB |
# of queries: 1700 |
| 2 |
Correct |
29 ms |
1048 KB |
# of queries: 1680 |
| 3 |
Correct |
25 ms |
1016 KB |
# of queries: 1788 |
| 4 |
Correct |
32 ms |
1012 KB |
# of queries: 1745 |
| 5 |
Correct |
31 ms |
1052 KB |
# of queries: 1763 |
| 6 |
Correct |
22 ms |
1096 KB |
# of queries: 1770 |
| 7 |
Correct |
20 ms |
1076 KB |
# of queries: 1767 |
| 8 |
Correct |
22 ms |
1020 KB |
# of queries: 1682 |
| 9 |
Correct |
15 ms |
1084 KB |
# of queries: 1775 |
| 10 |
Correct |
14 ms |
732 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 4 |
| 13 |
Correct |
0 ms |
208 KB |
# of queries: 7 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 14 |
| 15 |
Correct |
1 ms |
336 KB |
# of queries: 81 |
| 16 |
Correct |
3 ms |
396 KB |
# of queries: 170 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
952 KB |
# of queries: 1700 |
| 2 |
Correct |
29 ms |
1048 KB |
# of queries: 1680 |
| 3 |
Correct |
25 ms |
1016 KB |
# of queries: 1788 |
| 4 |
Correct |
32 ms |
1012 KB |
# of queries: 1745 |
| 5 |
Correct |
31 ms |
1052 KB |
# of queries: 1763 |
| 6 |
Correct |
22 ms |
1096 KB |
# of queries: 1770 |
| 7 |
Correct |
20 ms |
1076 KB |
# of queries: 1767 |
| 8 |
Correct |
22 ms |
1020 KB |
# of queries: 1682 |
| 9 |
Correct |
15 ms |
1084 KB |
# of queries: 1775 |
| 10 |
Correct |
14 ms |
732 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
208 KB |
# of queries: 4 |
| 13 |
Correct |
0 ms |
208 KB |
# of queries: 7 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 14 |
| 15 |
Correct |
1 ms |
336 KB |
# of queries: 81 |
| 16 |
Correct |
3 ms |
396 KB |
# of queries: 170 |
| 17 |
Correct |
188 ms |
4172 KB |
# of queries: 11124 |
| 18 |
Correct |
222 ms |
4032 KB |
# of queries: 11029 |
| 19 |
Correct |
184 ms |
4160 KB |
# of queries: 11087 |
| 20 |
Correct |
193 ms |
3932 KB |
# of queries: 10416 |
| 21 |
Correct |
177 ms |
3804 KB |
# of queries: 9812 |
| 22 |
Correct |
202 ms |
4196 KB |
# of queries: 11159 |
| 23 |
Correct |
215 ms |
4228 KB |
# of queries: 11139 |
| 24 |
Correct |
74 ms |
2240 KB |
# of queries: 5247 |
| 25 |
Correct |
201 ms |
3988 KB |
# of queries: 10880 |
| 26 |
Correct |
171 ms |
3860 KB |
# of queries: 10176 |
| 27 |
Correct |
72 ms |
2288 KB |
# of queries: 5201 |
| 28 |
Correct |
68 ms |
4288 KB |
# of queries: 3996 |
| 29 |
Correct |
65 ms |
4256 KB |
# of queries: 3992 |
| 30 |
Correct |
57 ms |
4320 KB |
# of queries: 3996 |
