oj.uz

답안 #213272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213272 2020-03-25T11:56:34 Z brcode 도서관 (JOI18_library) C++14
19 / 100
 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);
}*/

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 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)