# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
617438 | Ahmadsm2005 | Library (JOI18_library) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "library.h"
#include "grader.cpp"
using namespace std;
bool E[1000][1000],VIS[1000];
int CNT[1000],NN;
void DFS(int v,int L,int R){
if(VIS[v])return;
VIS[v] = 1;
for(int i = 0; i < NN; i += 1)if(E[i][v] && i >= L && i <= R)DFS(i,L,R);
}
int BS(int idx,int BL = -1){
int L = 0, R = idx - 1 -(BL == -1? 0 : 1), mid;
while(L <= R){
if(L == R){
E[idx][L - 1] = E[L - 1][idx] = 1;
//cout<<L<<endl;
return L;
}
vector<int>F(NN,0);
mid = (L + R) / 2;
int Z = 0;
for(int i = L; i <= mid; i += 1)F[i + (BL != -1 && i >= BL? 1 : 0)] = 1;
for(int i = L; i <= mid; i += 1){
if(!VIS[i + (BL != -1 && i >= BL? 1 : 0)])DFS(i + (BL != -1 && i >= BL? 1 : 0),L,mid),Z++;
}
if(Z == Query(F))L = mid + 1;
else R = mid - 1;
for(int i = 0; i < NN; i += 1)VIS[i] = 0;
}
}
void Solve(int N)
{
NN = N;
vector<int> M(N);
M[0] = 1;
int LST = 1;
for(int i = 1; i < N; i += 1){
M[i] = 1;
int A = Query(M);
if(A <= LST){
//cout<<"Hmm: "<<i + 1<<endl;
if(A == LST)BS(i);
else{
int Q = BS(i);
BS(i,Q);
}
LST = A;
}
else
LST = A;
}
int S = 0, P = -1;
for(int i = 0; i < N; i += 1)if(CNT[i] == 1){S = i;}
vector<int> res;
while(1){
res.push_back(S + 1);
//cout<<S + 1<<' ';
for(int i = 0; i < N; i += 1)if(i != P && E[S][i]){P = S, S = i; goto a;}
break;
a:;
}
//cout<<endl;
//cout<<res.size()<<endl;
Answer(res);
}