oj.uz

답안 #111451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111451 2019-05-15T11:46:11 Z igzi 도서관 (JOI18_library) C++17
100 / 100
 513 ms 684 KB 
#include <bits/stdc++.h>
#define maxN 1005
#include "library.h"

using namespace std;

vector <int> adj[maxN];
int N;

int upit(int l,int d,int x){
vector<int> v(N);
if(x!=-1) v[x-1]=1;
for(int i=l;i<=d;i++) v[i-1]=1;
return Query(v);
}

void resi1(int l,int d,int x){
if(l==d){
    adj[x].push_back(l);
    adj[l].push_back(x);
    return;
}
int m=(l+d)/2;
if(upit(l,m,x)-upit(l,m,-1)==0) resi1(l,m,x);
else resi1(m+1,d,x);
}

void resi2(int l,int d,int x){
int m=(l+d)/2;
int tmp=upit(l,m,x)-upit(l,m,-1);
if(tmp==-1) resi2(l,m,x);
if(tmp==1) resi2(m+1,d,x);
if(tmp==0) {resi1(l,m,x); resi1(m+1,d,x);}
}

vector <int> res;

void dfs(int n,int par){
res.push_back(n);
if(adj[n][0]!=par) dfs(adj[n][0],n);
else{
    if(adj[n].size()==1) return;
    dfs(adj[n][1],n);
}
}

void Solve(int n)
{
    N=n;
    if(n==1){
        res.push_back(1);
        Answer(res);
        return;
    }
	for(int i=2;i<=n;i++){
        int tmp=upit(1,i-1,i)-upit(1,i-1,-1);
        if(tmp==-1) resi2(1,i-1,i);
        if(tmp==0) resi1(1,i-1,i);
	}
	for(int i=1;i<=n;i++){
        if(adj[i].size()==1){
            dfs(i,-1);
            break;
        }
	}
	Answer(res);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 348 KB # of queries: 2730
2 Correct 58 ms 256 KB # of queries: 2798
3 Correct 46 ms 424 KB # of queries: 2864
4 Correct 60 ms 376 KB # of queries: 2898
5 Correct 54 ms 336 KB # of queries: 2884
6 Correct 26 ms 344 KB # of queries: 2850
7 Correct 51 ms 256 KB # of queries: 2940
8 Correct 34 ms 256 KB # of queries: 2796
9 Correct 49 ms 352 KB # of queries: 2930
10 Correct 30 ms 384 KB # of queries: 1712
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 2
13 Correct 3 ms 256 KB # of queries: 6
14 Correct 2 ms 428 KB # of queries: 12
15 Correct 2 ms 256 KB # of queries: 98
16 Correct 5 ms 384 KB # of queries: 230

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 348 KB # of queries: 2730
2 Correct 58 ms 256 KB # of queries: 2798
3 Correct 46 ms 424 KB # of queries: 2864
4 Correct 60 ms 376 KB # of queries: 2898
5 Correct 54 ms 336 KB # of queries: 2884
6 Correct 26 ms 344 KB # of queries: 2850
7 Correct 51 ms 256 KB # of queries: 2940
8 Correct 34 ms 256 KB # of queries: 2796
9 Correct 49 ms 352 KB # of queries: 2930
10 Correct 30 ms 384 KB # of queries: 1712
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 2
13 Correct 3 ms 256 KB # of queries: 6
14 Correct 2 ms 428 KB # of queries: 12
15 Correct 2 ms 256 KB # of queries: 98
16 Correct 5 ms 384 KB # of queries: 230
17 Correct 418 ms 612 KB # of queries: 19364
18 Correct 462 ms 448 KB # of queries: 19016
19 Correct 513 ms 472 KB # of queries: 19160
20 Correct 424 ms 384 KB # of queries: 17832
21 Correct 433 ms 480 KB # of queries: 16854
22 Correct 369 ms 596 KB # of queries: 19274
23 Correct 479 ms 684 KB # of queries: 19252
24 Correct 185 ms 380 KB # of queries: 8846
25 Correct 500 ms 348 KB # of queries: 18830
26 Correct 365 ms 476 KB # of queries: 17506
27 Correct 167 ms 376 KB # of queries: 8832
28 Correct 478 ms 504 KB # of queries: 17954
29 Correct 480 ms 608 KB # of queries: 17934
30 Correct 467 ms 484 KB # of queries: 17954