oj.uz

답안 #213248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213248 2020-03-25T11:13:48 Z brcode 도서관 (JOI18_library) C++14
0 / 100
 1077 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]);
        
    }
    
    if(check && deg[x] == 0){
        toQuery(x,d1,sz);
        return;
    }
    
    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
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 268 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 262 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Incorrect 41 ms 256 KB Wrong Answer [4]
11 Correct 5 ms 384 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 3
14 Correct 5 ms 384 KB # of queries: 6
15 Incorrect 6 ms 384 KB Wrong Answer [8]
16 Runtime error 183 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 268 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 262 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Incorrect 41 ms 256 KB Wrong Answer [4]
11 Correct 5 ms 384 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 3
14 Correct 5 ms 384 KB # of queries: 6
15 Incorrect 6 ms 384 KB Wrong Answer [8]
16 Runtime error 183 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 883 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 696 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 876 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 702 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 749 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 827 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 716 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 509 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 744 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 692 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 423 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 1077 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 1062 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 1068 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)