| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213272 |
2020-03-25T11:56:34 Z |
brcode |
Library (JOI18_library) |
C++14 |
|
1094 ms |
262148 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];
/*int Query(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 toQuery(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= Query(tempq);
}else{
A=1;
}
tempq[x-1] = 1;
int nxt = Query(tempq);
if(nxt<=A){
toQuery(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(Query(tempq)==1){
toQuery(x,d1,sz);
}
return;
}
if(check && deg[x]==0){
toQuery(x,d1,sz);
return;
}
B= Query(tempq);
tempq[x-1] = 1;
nxt = Query(tempq);
if(nxt<=B){
toQuery(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(Query(tempq) == 1){
toQuery(i,l,n);
}
}else{
for(int x:l){
tempq[x-1] = 1;
}
int A = Query(tempq);
tempq[i-1] = 1;
int nxt = Query(tempq);
if(nxt<=A){
toQuery(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(Query(tempq) == 1){
toQuery(i,r,n);
}
}else{
for(int x:r){
tempq[x-1] = 1;
}
int A = Query(tempq);
tempq[i-1] = 1;
int nxt = Query(tempq);
if(nxt<=A){
toQuery(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 |
65 ms |
384 KB |
# of queries: 3975 |
| 2 |
Correct |
70 ms |
384 KB |
# of queries: 4147 |
| 3 |
Correct |
72 ms |
384 KB |
# of queries: 4255 |
| 4 |
Correct |
75 ms |
384 KB |
# of queries: 4359 |
| 5 |
Correct |
87 ms |
384 KB |
# of queries: 4350 |
| 6 |
Correct |
91 ms |
384 KB |
# of queries: 4288 |
| 7 |
Correct |
76 ms |
384 KB |
# of queries: 4371 |
| 8 |
Correct |
67 ms |
384 KB |
# of queries: 4169 |
| 9 |
Correct |
93 ms |
384 KB |
# of queries: 4284 |
| 10 |
Correct |
42 ms |
384 KB |
# of queries: 2479 |
| 11 |
Correct |
5 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 10 |
| 15 |
Correct |
6 ms |
384 KB |
# of queries: 117 |
| 16 |
Correct |
9 ms |
384 KB |
# of queries: 292 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
384 KB |
# of queries: 3975 |
| 2 |
Correct |
70 ms |
384 KB |
# of queries: 4147 |
| 3 |
Correct |
72 ms |
384 KB |
# of queries: 4255 |
| 4 |
Correct |
75 ms |
384 KB |
# of queries: 4359 |
| 5 |
Correct |
87 ms |
384 KB |
# of queries: 4350 |
| 6 |
Correct |
91 ms |
384 KB |
# of queries: 4288 |
| 7 |
Correct |
76 ms |
384 KB |
# of queries: 4371 |
| 8 |
Correct |
67 ms |
384 KB |
# of queries: 4169 |
| 9 |
Correct |
93 ms |
384 KB |
# of queries: 4284 |
| 10 |
Correct |
42 ms |
384 KB |
# of queries: 2479 |
| 11 |
Correct |
5 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 1 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 10 |
| 15 |
Correct |
6 ms |
384 KB |
# of queries: 117 |
| 16 |
Correct |
9 ms |
384 KB |
# of queries: 292 |
| 17 |
Runtime error |
749 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
748 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
750 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
798 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
674 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
759 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
730 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 24 |
Correct |
267 ms |
384 KB |
# of queries: 13488 |
| 25 |
Runtime error |
752 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 26 |
Runtime error |
713 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 |
Correct |
323 ms |
384 KB |
# of queries: 13497 |
| 28 |
Runtime error |
1075 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 29 |
Runtime error |
1094 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 30 |
Runtime error |
1080 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
