| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 213289 | brcode | 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.
#include <iostream>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
deque<int> l;
vector<int> g[MAXN];
deque<int> r;
vector<int> ord;
int cnt;
vector<int> rem;
vector<int> templ;
vector<int> tempr;
deque<int> curr;
vector<int> tempq;
int deg[MAXN];
map<bitset<int>,int> m1;
/*int willQuery(vector<int> x){
for(int y:x){
cout<<y<<" ";
}
cnt++;
cout<<endl;
if(cnt == 1){
cout<<2<<endl;
return 2;
}
if(cnt == 2){
cout<<1<<endl;
return 1;
}
if(cnt==3){
cout<<2<<endl;
return 2;
}
if(cnt==4){
cout<<3<<endl;
return 3;
}
if(cnt==5){
cout<<2<<endl;
return 2;
}
if(cnt == 6){
cout<<2<<endl;
return 0;
}
if(cnt==7){
cout<<1<<endl;
return 0;
}
if(cnt ==8){
cout<<1<<endl;
return 0;
}
if(cnt==9){
cout<<1<<endl;
return 1;
}
if(cnt==10){
cout<<2<<endl;
return 2;
}
if(cnt == 11){
cout<<1<<endl;
return 0;
}
return 1;
}
void Answer(vector<int> x){
for(int y:x){
cout<<y<<" ";
}
cout<<endl;
}*/
void willQuery(vector<int> x){
bitset<1010> a;
for(int i=0;i<x.size();i++){
if(x[i]){
a.set(x[i]);
}
}
if(m1[a]){
return a;
}else{
m1[a] = Query(x);
}
}
void towillQuery(int x,deque<int> v1,int sz){
int n = v1.size();
for(int i=0;i<sz;i++){
tempq[i] = 0;
//cout<<sz<<endl;
}
if(n==1){
g[x].push_back(v1[0]);
g[v1[0]].push_back(x);
deg[x]++;
deg[v1[0]]++;
if(deg[v1[0]] == 2){
//cout<<x<<" "<<v1[0]<<endl;
rem.push_back(v1[0]);
}
return;
}
bool check = false;
deque<int> d1;
for(int i=0;i<(n/2);i++){
tempq[v1[i]-1] = 1;
tempq[x-1] = 0;
d1.push_back(v1[i]);
}
int A;
if(d1.size()>1){
A= willQuery(tempq);
}else{
A=1;
}
tempq[x-1] = 1;
int nxt = willQuery(tempq);
if(nxt<=A){
towillQuery(x,d1,sz);
}else{
check = true;
}
d1.clear();
for(int i=0;i<(n/2);i++){
tempq[v1[i]-1] = 0;
}
for(int i=(n/2);i<(n);i++){
tempq[v1[i]-1] = 1;
// cout<<v1[i-1]<<" ";
tempq[x-1] = 0;
d1.push_back(v1[i]);
}
int B;
if(d1.size() == 0){
return;
}
if(d1.size() == 1){
tempq[x-1] = 1;
if(willQuery(tempq)==1){
towillQuery(x,d1,sz);
}
return;
}
if(check && deg[x]==0){
towillQuery(x,d1,sz);
return;
}
B= willQuery(tempq);
tempq[x-1] = 1;
nxt = willQuery(tempq);
if(nxt<=B){
towillQuery(x,d1,sz);
}
}
void dfs(int curr,int par){
ord.push_back(curr);
for(int x:g[curr]){
if(x!=par){
dfs(x,curr);
}
}
}
void clearQ(int n){
for(int i=0;i<n;i++){
tempq[i] = 0;
}
}
void Solve(int N){
int n = N;
if(n==1){
vector<int> res;
res.push_back(1);
Answer(res);
return;
}
for(int i=1;i<=n;i++){
//tempq = vector we use for Querying
tempq.push_back(0);
}
for(int i=1;i<=(N/2);i++){
l.push_back(i);
//l subarray
}
for(int i=(N/2)+1;i<=N;i++){
r.push_back(i);
//r subarray
}
for(int i=1;i<=n;i++){
if(i<=(n/2)){
if(l.size() && l.front() == i){
l.pop_front();
}
}else{
if(r.size() && r.front() == i){
r.pop_front();
}
}
clearQ(n);
if(l.size()){
if(l.size()==1){
tempq[l[0]-1] = 1;
tempq[i-1] = 1;
if(willQuery(tempq) == 1){
towillQuery(i,l,n);
}
}else{
for(int x:l){
tempq[x-1] = 1;
}
int A = willQuery(tempq);
tempq[i-1] = 1;
int nxt = willQuery(tempq);
if(nxt<=A){
towillQuery(i,l,n);
}
}
}
clearQ(n);
for(int x:rem){
//cout<<123<<endl;
if(x<=(N/2)){
for(int y:l){
if(y==x){
continue;
}else{
templ.push_back(y);
}
}
l.clear();
for(int y:templ){
l.push_back(y);
}
templ.clear();
}else{
for(int y:r){
if(y==x){
continue;
}else{
tempr.push_back(y);
}
}
r.clear();
for(int y:tempr){
r.push_back(y);
}
tempr.clear();
}
}
rem.clear();
clearQ(n);
if(r.size()){
if(r.size() == 1){
tempq[r[0]-1] = 1;
tempq[i-1] = 1;
if(willQuery(tempq) == 1){
towillQuery(i,r,n);
}
}else{
for(int x:r){
tempq[x-1] = 1;
}
int A = willQuery(tempq);
tempq[i-1] = 1;
int nxt = willQuery(tempq);
if(nxt<=A){
towillQuery(i,r,n);
}
}
}
clearQ(n);
for(int x:rem){
if(x<=(N/2)){
for(int y:l){
if(y==x){
continue;
}else{
templ.push_back(y);
}
}
l.clear();
for(int y:templ){
l.push_back(y);
}
templ.clear();
}else{
for(int y:r){
if(y==x){
continue;
}else{
tempr.push_back(y);
}
}
r.clear();
for(int y:tempr){
r.push_back(y);
}
tempr.clear();
}
}
rem.clear();
}
for(int i=1;i<=n;i++){
if(deg[i] == 1){
dfs(i,i);
break;
}
}
Answer(ord);
}
/*int main(){
Solve(5);
}*/