#include <cstdio>
#include <vector>
#include <set>
#include "library.h"
#include <cstring>
#include <cassert>
#ifdef atom
#include "grader.cpp"
#endif
using namespace std;
struct cc
{
int left, right;
set<int> mem;
};
vector< cc > comps;
vector<int> input;
int lhs[1005], rhs[1005];
int n;
void clear()
{
input.assign(n, 0);
}
void insert(cc x)
{
for(auto k : x.mem) input[k-1] = 1;
}
int ask()
{
return Query(input);
}
int dx(int from, int to, int work)
{
int bf = to-from+1;
clear();
for(int i = from; i<= to; i++) insert(comps[i]);
input[work-1] = 1;
int res = ask();
return res-bf;
}
void join(int index, int work)
{
cc &here = comps[index];
clear();
input[here.left-1] = 1; input[work-1] = 1;
int res = ask();
if(res == 1)
{
//printf("this case\n");
//work here
rhs[work] = here.left, lhs[here.left] = work;
here.left = work;
}
else
{
//here work
lhs[work] = here.right, rhs[here.right] = work;
here.right = work;
}
here.mem.insert(work);
}
void join2(int id1, int id2, int work)
{
cc cc1 = comps[id1], cc2 = comps[id2];
if(cc1.mem.size()< cc2.mem.size()) swap(cc1, cc2);
clear();
input[cc1.left-1] = 1; input[work-1] = 1;
int res = ask();
cc nouv;
for(auto x : cc1.mem) nouv.mem.insert(x);
for(auto x : cc2.mem) nouv.mem.insert(x);
nouv.mem.insert(work);
if(res == 1)
{
//cc2 work cc1
//printf("this case\n");
rhs[cc2.right] = work; lhs[cc1.left] = work;
lhs[work] = cc2.right; rhs[work] = cc1.left;
nouv.left = cc2.left; nouv.right = cc1.right;
}
else
{
//cc1 work cc2
rhs[cc1.right] = work; lhs[cc2.left] = work;
lhs[work] = cc1.right; rhs[work] = cc2.left;
nouv.left = cc1.left; nouv.right = cc2.right;
}
if(id1> id2) swap(id1, id2);
comps.erase(comps.begin()+id2);
comps.erase(comps.begin()+id1);
comps.push_back(nouv);
}
int lookfor(int from, int to, int work)
{
if(from == to) return from;
int mid = (from+to)/2;
int res = dx(from, mid, work);
if(res == 0) return lookfor(from, mid, work);
return lookfor(mid+1, to, work);
}
#define ii pair<int, int>
ii lookfor2(int from, int to, int work)
{
if(from+1 == to) return ii(from, to);
int mid = (from+to)/2;
int res = dx(from, mid, work);
if(res == -1) return lookfor2(from, mid, work);
if(res == 0) return ii(lookfor(from, mid, work), lookfor(mid+1, to, work));
return lookfor2(mid+1, to, work);
}
void Solve(int N)
{
n = N;
input.resize(N);
memset(lhs, -1, sizeof lhs); memset(rhs, -1, sizeof rhs);
cc one; one.left = one.right = 1; one.mem.insert(1);
comps.push_back(one);
for(int i = 2; i<= N; i++)
{
int res = dx(0, comps.size()-1, i);
//printf("%d: %d\n", i, res);
if(res == 1)
{
cc nouvelle; nouvelle.left = nouvelle.right = i; nouvelle.mem.insert(i);
comps.push_back(nouvelle);
//printf("lone component %d\n", comps.size()-1);
}
else if(res == 0)
{
int k = lookfor(0, comps.size()-1, i);
//printf("attach with %d\n", k);
join(k, i);
}
else
{
ii tt = lookfor2(0, comps.size()-1, i);
//printf("joined %d %d\n", tt.first, tt.second);
join2(tt.first, tt.second, i);
}
//printf("now %d comps\n", comps.size());
}
//for(int i = 1; i<= n; i++) printf("%d %d\n", lhs[i], rhs[i]);
int st = -1;
for(int i = 1; i<= n; i++) if(lhs[i] == -1) st = i;
vector<int> res;
while(st != -1)
{
res.push_back(st);
st = rhs[st];
}
//for(auto x : res) printf("%d ", x);
Answer(res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
376 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
376 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
