| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213328 |
2020-03-25T15:14:36 Z |
brcode |
Library (JOI18_library) |
C++14 |
|
1037 ms |
79152 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<vector<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;
}*/
int willQuery(vector<int> x){
if(m1[x]){
return m1[x];
}else{
return m1[x] = Query(x);
}
}
void towillQuery(int x,deque<int> v1,int sz){
if(deg[x] == 2){
return;
}
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]);
}
if(deg[x] == 2){
return;
}
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);
bool ok = false;
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{
ok=true;
}
}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);
}else{
ok = true;
}
}
}
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;
}
if(!ok){
towillQuery(i,r,n);
}else{
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);
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
2552 KB |
# of queries: 2536 |
| 2 |
Correct |
52 ms |
2496 KB |
# of queries: 2563 |
| 3 |
Correct |
67 ms |
2852 KB |
# of queries: 2790 |
| 4 |
Correct |
60 ms |
2808 KB |
# of queries: 2748 |
| 5 |
Correct |
58 ms |
2808 KB |
# of queries: 2705 |
| 6 |
Correct |
68 ms |
2756 KB |
# of queries: 2698 |
| 7 |
Correct |
62 ms |
2808 KB |
# of queries: 2755 |
| 8 |
Correct |
58 ms |
2556 KB |
# of queries: 2606 |
| 9 |
Correct |
49 ms |
2708 KB |
# of queries: 2725 |
| 10 |
Correct |
31 ms |
1272 KB |
# of queries: 1525 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
4 ms |
384 KB |
# of queries: 3 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
384 KB |
# of queries: 64 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 173 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
2552 KB |
# of queries: 2536 |
| 2 |
Correct |
52 ms |
2496 KB |
# of queries: 2563 |
| 3 |
Correct |
67 ms |
2852 KB |
# of queries: 2790 |
| 4 |
Correct |
60 ms |
2808 KB |
# of queries: 2748 |
| 5 |
Correct |
58 ms |
2808 KB |
# of queries: 2705 |
| 6 |
Correct |
68 ms |
2756 KB |
# of queries: 2698 |
| 7 |
Correct |
62 ms |
2808 KB |
# of queries: 2755 |
| 8 |
Correct |
58 ms |
2556 KB |
# of queries: 2606 |
| 9 |
Correct |
49 ms |
2708 KB |
# of queries: 2725 |
| 10 |
Correct |
31 ms |
1272 KB |
# of queries: 1525 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
4 ms |
384 KB |
# of queries: 3 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
384 KB |
# of queries: 64 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 173 |
| 17 |
Correct |
1014 ms |
78748 KB |
# of queries: 19466 |
| 18 |
Correct |
991 ms |
76408 KB |
# of queries: 19125 |
| 19 |
Correct |
988 ms |
78136 KB |
# of queries: 19313 |
| 20 |
Correct |
910 ms |
69380 KB |
# of queries: 18196 |
| 21 |
Correct |
839 ms |
61728 KB |
# of queries: 17058 |
| 22 |
Correct |
1037 ms |
79152 KB |
# of queries: 19566 |
| 23 |
Correct |
1012 ms |
78044 KB |
# of queries: 19279 |
| 24 |
Correct |
280 ms |
18424 KB |
# of queries: 8580 |
| 25 |
Correct |
982 ms |
75896 KB |
# of queries: 19139 |
| 26 |
Correct |
897 ms |
66736 KB |
# of queries: 17807 |
| 27 |
Correct |
274 ms |
18588 KB |
# of queries: 8679 |
| 28 |
Correct |
634 ms |
48748 KB |
# of queries: 12029 |
| 29 |
Correct |
629 ms |
48760 KB |
# of queries: 12013 |
| 30 |
Correct |
714 ms |
48812 KB |
# of queries: 12029 |
