# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
630271 | codr0 | Library (JOI18_library) | C++14 | 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.
// Code by Parsa Eslami
#include <bits/stdc++.h>
#include "library.h"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define err(x) cerr<<#x<<" : "<<x<<'\n'
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
using namespace std;
int query(vector<int> x){
int t=0;
FOR(i,0,SZ(x)-1) t+=x[i];
return (t-Query(x));
}
void Solve(int n){
vector<int> ans;
if(n==1){
ans.pb(1);
return ans;
}
FOR(j,0,n-1){
vector<int> m(n);
FOR(w,0,n-1) m[w]=(w!=j);
if(query(m)==n-2){
ans.pb(j+1);
break;
}
}
vector<int> vc2;
FOR(i,0,n-1) if(i!=(ans.back()-1)) vc2.pb(i);
while(!vc2.empty()){
vector<int> vc=vc2;
while(SZ(vc)!=1){
int mid=SZ(vc)/2;
vector<int> m(n);
FOR(w,0,n-1) m[w]=0;
FOR(j,0,mid-1) m[vc[j]]=1;
int a1=query(m);
m[ans.back()-1]=1;
int a2=query(m);
if(a2-a1==1){
vector<int> vc0;
FOR(j,0,mid-1) vc0.pb(vc[j]);
vc=vc0;
}else{
vector<int> vc0;
FOR(j,mid,SZ(vc)-1) vc0.pb(vc[j]);
vc=vc0;
}
}
ans.pb(vc.back()+1);
vector<int> vc0;
FOR(i,0,SZ(vc2)-1) if(vc2[i]!=vc.back()) vc0.pb(vc2[i]);
vc2=vc0;
}
Answer(ans);
}