| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 630058 |
2022-08-15T15:18:55 Z |
Arnch |
Library (JOI18_library) |
C++17 |
|
2000 ms |
676 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;
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();
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();
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();
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();
continue;
}
mark[u2] = mark[v2] = 0;
}
}
/*for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(e[i][j]) {
cout<<"^^" <<i <<' ' <<j <<endl;
}*/
vector<int> res;
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(Sz(res) < n) {
int u = res.back();
for(int j = 1; j <= n; j++) {
if(e[u][j] && !vis[j]) {
res.push_back(j);
vis[j] = 1;
break;
}
}
}
Answer(res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3003 ms |
676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3003 ms |
676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
