#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int d[1002][2],tmp=0,tt;
vector<int> emp;
vector<int> M,res;
int bs(vector<int> v,int t,int k){
//for(auto it:v) cout<<it<<" ";cout<<endl;
int sum=0;
for(auto it:v) sum+=it;
if(!sum) return -1;
//cout<<sum<<"&";
if(sum==2) {
for(int i=0;i<v.size();i++)if(v[i] && i!=t) {
if(d[i][0]==i && d[t][1]==t) {swap(d[i][0],d[t][1]);} else {swap(d[i][1],d[t][0]);}
//cout<<"#"<<d[i][0]<<" "<<d[i][1]<<" "<<i<<"#";cout<<"#";cout<<"["<<i<<" "<<t<<"]";cout<<"{"<<i<<" "<<t<<"}";
if(d[i][0]!=i && d[i][1]!=i) {M[i]=0;}
if(d[t][0]!=t && d[t][1]!=t) {tmp++;}
return i;
}
}
int cnt=0,j=0,k1=0;
int N=v.size();
vector<int> v1=emp;
v1[t]=1;//cout<<k<<":";
for(int i=0;i<N;i++){
if(i==t) continue;
cnt+=v[i];
if(cnt==2) {
cnt=0;
v[i]=0;
if(!v[d[i][0]] && !v[d[i][1]]) k--;
if(!v1[d[i][0]] && !v1[d[i][1]]) k1++;
v1[i]=1;
}
}//cout<<"("<<k<<" "<<k1<<" "<<Query(v)<<")\n";
if(Query(v)<=k) return bs(v,t,k); else return bs(v1,t,k1);
}
void Solve(int N)
{
for(int i=0;i<N;i++){
d[i][0]=i;
d[i][1]=i;
M.push_back(0);
}
emp=M;
M[0]=1;
int k=1,j;
for(int i=1;i<N;i++){
k=0;
for(int i=0;i<N;i++){
if(M[i]){
//if(d[i][0]==i && d[i][1]==i) k++;
if(d[i][0]==i) k++; else
if(d[i][1]==i && !M[d[i][0]]) k++;
}
}
M[i]=1;
int l=Query(M);
//cout<<l<<" "<<k<<":"<<endl;
//for(auto it:M) cout<<it<<" ";cout<<endl;
if(l>k) {k++;continue;}
if(l<=k){
j=bs(M,i,k);//cout<<"*"<<j<<" "<<tmp<<"*";
if(l==k){k-=tmp;tmp=0;continue;}
//k-=tmp;tmp=0;
}
//cout<<"!!!";
tt=M[j];
M[j]=0;
//tt=0;
if(d[j][0]==j || d[j][0]==i) k--; else
if((d[j][1]==j || d[j][1]==i) && (!M[d[j][0]] ||d[j][0]==i)) k--;//cout<<"&&&"<<k<<" "<<d[j][0]<<" "<<d[j][1]<<" "<<j<<"&&";
bs(M,i,k);
//if(d[j][0]==j || d[j][1]==j) {k++;}
//k-=tmp;tmp=0;
M[j]=tt;
M[i]=0;
}
int idx=0,pr=-1;
for(int i=0;i<N;i++){
if(d[i][0]==i || d[i][1]==i) {idx=i;break;}
}//cout<<idx<<"%%";
for(int i=0;i<N;i++){
res.push_back(idx+1);
//cout<<idx+1<<" ";
if(d[idx][0]!=idx && d[idx][0]!=pr){pr=idx;idx=d[idx][0];}
else {pr=idx;idx=d[idx][1];}
}
Answer(res);
}
Compilation message
library.cpp: In function 'int bs(std::vector<int>, int, int)':
library.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++)if(v[i] && i!=t) {
~^~~~~~~~~
library.cpp:22:15: warning: unused variable 'j' [-Wunused-variable]
int cnt=0,j=0,k1=0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
376 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
376 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
