| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213253 |
2020-03-25T11:19:12 Z |
brcode |
Library (JOI18_library) |
C++14 |
|
1249 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){
B=1;
}else{
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{
toQuery(i,l,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{
toQuery(i,r,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: In function 'void toQuery(int, std::deque<int>, int)':
library.cpp:96:10: warning: variable 'check' set but not used [-Wunused-but-set-variable]
bool check = false;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
384 KB |
# of queries: 4311 |
| 2 |
Correct |
86 ms |
384 KB |
# of queries: 4396 |
| 3 |
Correct |
77 ms |
384 KB |
# of queries: 4546 |
| 4 |
Correct |
85 ms |
384 KB |
# of queries: 4568 |
| 5 |
Correct |
88 ms |
384 KB |
# of queries: 4591 |
| 6 |
Correct |
92 ms |
384 KB |
# of queries: 4519 |
| 7 |
Correct |
102 ms |
384 KB |
# of queries: 4594 |
| 8 |
Correct |
82 ms |
384 KB |
# of queries: 4356 |
| 9 |
Correct |
98 ms |
384 KB |
# of queries: 4601 |
| 10 |
Correct |
52 ms |
384 KB |
# of queries: 2624 |
| 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: 3 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 6 |
| 15 |
Correct |
7 ms |
384 KB |
# of queries: 110 |
| 16 |
Correct |
10 ms |
384 KB |
# of queries: 291 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
384 KB |
# of queries: 4311 |
| 2 |
Correct |
86 ms |
384 KB |
# of queries: 4396 |
| 3 |
Correct |
77 ms |
384 KB |
# of queries: 4546 |
| 4 |
Correct |
85 ms |
384 KB |
# of queries: 4568 |
| 5 |
Correct |
88 ms |
384 KB |
# of queries: 4591 |
| 6 |
Correct |
92 ms |
384 KB |
# of queries: 4519 |
| 7 |
Correct |
102 ms |
384 KB |
# of queries: 4594 |
| 8 |
Correct |
82 ms |
384 KB |
# of queries: 4356 |
| 9 |
Correct |
98 ms |
384 KB |
# of queries: 4601 |
| 10 |
Correct |
52 ms |
384 KB |
# of queries: 2624 |
| 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: 3 |
| 14 |
Correct |
5 ms |
384 KB |
# of queries: 6 |
| 15 |
Correct |
7 ms |
384 KB |
# of queries: 110 |
| 16 |
Correct |
10 ms |
384 KB |
# of queries: 291 |
| 17 |
Runtime error |
910 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
866 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
860 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
859 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
845 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
747 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
735 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 24 |
Correct |
356 ms |
384 KB |
# of queries: 14442 |
| 25 |
Runtime error |
979 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 26 |
Runtime error |
820 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 |
Correct |
285 ms |
384 KB |
# of queries: 14531 |
| 28 |
Runtime error |
1095 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 29 |
Runtime error |
1225 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 30 |
Runtime error |
1249 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
