Submission #535767

#	Time	Username	Problem	Language	Result	Execution time	Memory
535767		79brue	Library (JOI18_library)	C++14	100 / 100	238 ms	464 KiB

library

#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 / 19
• Subtask 2: 81 / 81