oj.uz

답안 #535767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535767 2022-03-11T06:57:35 Z 79brue 도서관 (JOI18_library) C++14
100 / 100
 238 ms 464 KB 
#include "library.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> queryVec;
vector<int> link[1002];
bool visited[1002];
vector<int> ans;

void dfs(int x){
    visited[x] = 1;
    ans.push_back(x);
    for(auto y: link[x]){
        if(visited[y]) continue;
        dfs(y);
    }
}

void findLink(int l, int r, int i){
    if(l==r){
        link[i].push_back(l);
        link[l].push_back(i);
        return;
    }
    int m = (l+r)>>1;
    for(int x=0; x<n; x++) queryVec[x] = 0;
    for(int x=m+1; x<=r; x++) queryVec[x-1] = 1;
    queryVec[i-1] = 1;

    int expected = (r-m) + 1;
    for(int x=m+1; x<=r; x++) for(auto y: link[x]) if(x<=y && m<y && y<=r) expected--;

    if(expected == Query(queryVec)) findLink(l, m, i);
    else findLink(m+1, r, i);
}

void Solve(int N){
    n=N;
    queryVec.resize(n);

    if(n<=2){
        for(int i=1; i<=n; i++) ans.push_back(i);
        Answer(ans);
        return;
    }

    int prv = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++) queryVec[j-1] = 1;
        for(int j=i+1; j<=n; j++) queryVec[j-1] = 0;
        int ret = Query(queryVec);

        if(ret == prv + 1){
            prv = ret;
            continue;
        }

        if(ret == prv){ /// 인접한 것이 이전에 하나 존재했다
            findLink(1, i-1, i);
        }
        else if(ret == prv-1){ /// 인접한 것이 이전에 두개 존재했다
            findLink(1, i-1, i);
            findLink(1, link[i][0]-1, i);
        }
        else exit(1);
        prv = ret;
    }

    for(int i=1; i<=n; i++){
        if((int)link[i].size() == 1){
            dfs(i);
            break;
        }
    }
    Answer(ans);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 252 KB # of queries: 1454
2 Correct 21 ms 308 KB # of queries: 1465
3 Correct 21 ms 208 KB # of queries: 1539
4 Correct 20 ms 208 KB # of queries: 1535
5 Correct 22 ms 208 KB # of queries: 1537
6 Correct 21 ms 448 KB # of queries: 1528
7 Correct 14 ms 324 KB # of queries: 1542
8 Correct 21 ms 324 KB # of queries: 1475
9 Correct 25 ms 208 KB # of queries: 1545
10 Correct 13 ms 324 KB # of queries: 904
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 2 ms 208 KB # of queries: 55
16 Correct 3 ms 208 KB # of queries: 125

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 252 KB # of queries: 1454
2 Correct 21 ms 308 KB # of queries: 1465
3 Correct 21 ms 208 KB # of queries: 1539
4 Correct 20 ms 208 KB # of queries: 1535
5 Correct 22 ms 208 KB # of queries: 1537
6 Correct 21 ms 448 KB # of queries: 1528
7 Correct 14 ms 324 KB # of queries: 1542
8 Correct 21 ms 324 KB # of queries: 1475
9 Correct 25 ms 208 KB # of queries: 1545
10 Correct 13 ms 324 KB # of queries: 904
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 2 ms 208 KB # of queries: 55
16 Correct 3 ms 208 KB # of queries: 125
17 Correct 215 ms 344 KB # of queries: 10060
18 Correct 235 ms 340 KB # of queries: 9933
19 Correct 214 ms 344 KB # of queries: 10057
20 Correct 214 ms 336 KB # of queries: 9367
21 Correct 198 ms 308 KB # of queries: 8826
22 Correct 234 ms 464 KB # of queries: 10053
23 Correct 238 ms 444 KB # of queries: 10042
24 Correct 76 ms 460 KB # of queries: 4651
25 Correct 222 ms 456 KB # of queries: 9823
26 Correct 217 ms 340 KB # of queries: 9200
27 Correct 78 ms 316 KB # of queries: 4623
28 Correct 195 ms 336 KB # of queries: 8978
29 Correct 213 ms 456 KB # of queries: 8968
30 Correct 199 ms 336 KB # of queries: 8978