oj.uz

Submission #213243

# Submission time Handle Problem Language Result Execution time Memory
213243 2020-03-25T10:56:34 Z brcode Library (JOI18_library) C++14
19 / 100
 1213 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;
    }

    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);
    }
    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);
}*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 384 KB # of queries: 4311
2 Correct 75 ms 384 KB # of queries: 4396
3 Correct 77 ms 384 KB # of queries: 4546
4 Correct 97 ms 384 KB # of queries: 4568
5 Correct 94 ms 256 KB # of queries: 4591
6 Correct 75 ms 384 KB # of queries: 4519
7 Correct 82 ms 256 KB # of queries: 4594
8 Correct 72 ms 384 KB # of queries: 4356
9 Correct 78 ms 452 KB # of queries: 4601
10 Correct 47 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 9 ms 384 KB # of queries: 291

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 384 KB # of queries: 4311
2 Correct 75 ms 384 KB # of queries: 4396
3 Correct 77 ms 384 KB # of queries: 4546
4 Correct 97 ms 384 KB # of queries: 4568
5 Correct 94 ms 256 KB # of queries: 4591
6 Correct 75 ms 384 KB # of queries: 4519
7 Correct 82 ms 256 KB # of queries: 4594
8 Correct 72 ms 384 KB # of queries: 4356
9 Correct 78 ms 452 KB # of queries: 4601
10 Correct 47 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 9 ms 384 KB # of queries: 291
17 Runtime error 756 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 743 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 765 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 722 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 686 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 761 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 765 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Correct 284 ms 384 KB # of queries: 14442
25 Runtime error 795 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 729 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Correct 272 ms 384 KB # of queries: 14531
28 Runtime error 1213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 1203 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 1116 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)