| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213288 |
2020-03-25T12:12:45 Z |
brcode |
Library (JOI18_library) |
C++14 |
|
0 ms |
0 KB |
#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<int> 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);
}*/
Compilation message
library.cpp:18:15: error: type/value mismatch at argument 1 in template parameter list for 'template<long unsigned int _Nb> class std::bitset'
map<bitset<int>,int> m1;
^
library.cpp:18:15: note: expected a constant of type 'long unsigned int', got 'int'
library.cpp:18:20: error: template argument 1 is invalid
map<bitset<int>,int> m1;
^
library.cpp:18:20: error: template argument 3 is invalid
library.cpp:18:20: error: template argument 4 is invalid
library.cpp: In function 'void willQuery(std::vector<int>)':
library.cpp:80:15: error: type/value mismatch at argument 1 in template parameter list for 'template<long unsigned int _Nb> class std::bitset'
bitset<int> a;
^
library.cpp:80:15: note: expected a constant of type 'long unsigned int', got 'int'
library.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<x.size();i++){
~^~~~~~~~~
library.cpp:83:15: error: request for member 'set' in 'a', which is of non-class type 'int'
a.set(x[i]);
^~~
library.cpp:86:12: error: invalid types 'int[int]' for array subscript
if(m1[a]){
^
library.cpp:87:16: error: return-statement with a value, in function returning 'void' [-fpermissive]
return a;
^
library.cpp:89:13: error: invalid types 'int[int]' for array subscript
m1[a] = Query(x);
^
library.cpp: In function 'void towillQuery(int, std::deque<int>, int)':
library.cpp:126:27: error: void value not ignored as it ought to be
A= willQuery(tempq);
^
library.cpp:131:30: error: void value not ignored as it ought to be
int nxt = willQuery(tempq);
^
library.cpp:158:28: error: invalid operands of types 'void' and 'int' to binary 'operator=='
if(willQuery(tempq)==1){
~~~~~~~~~~~~~~~~^~~
library.cpp:168:23: error: void value not ignored as it ought to be
B= willQuery(tempq);
^
library.cpp:171:26: error: void value not ignored as it ought to be
nxt = willQuery(tempq);
^
library.cpp: In function 'void Solve(int)':
library.cpp:233:37: error: invalid operands of types 'void' and 'int' to binary 'operator=='
if(willQuery(tempq) == 1){
~~~~~~~~~~~~~~~~~^~~~
library.cpp:242:40: error: void value not ignored as it ought to be
int A = willQuery(tempq);
^
library.cpp:244:42: error: void value not ignored as it ought to be
int nxt = willQuery(tempq);
^
library.cpp:290:37: error: invalid operands of types 'void' and 'int' to binary 'operator=='
if(willQuery(tempq) == 1){
~~~~~~~~~~~~~~~~~^~~~
library.cpp:298:40: error: void value not ignored as it ought to be
int A = willQuery(tempq);
^
library.cpp:300:42: error: void value not ignored as it ought to be
int nxt = willQuery(tempq);
^
