제출 #1207032

#제출 시각아이디문제언어결과실행 시간메모리
1207032VMaksimoski008도서관 (JOI18_library)C++20
0 / 100
12 ms1212 KiB
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

vector<int> g[1005], ans;
int n, edge[1005][1005], vis[1005];

int ask(int l, int r) {
    vector<int> a(n);
    for(int i=l; i<=r; i++) a[i-1] = 1;
    return Query(a);
}

int get_cmp(int l, int r) {
    int cmp = r-l+1;
    for(int i=l; i<=r; i++)
        for(int j=i+1; j<=r; j++) cmp -= edge[i][j];
    return cmp;
}

void dfs(int u) {
    vis[u] = 1;
    ans.push_back(u);
    for(int v : g[u]) if(!vis[v]) dfs(v);
}

void Solve(int N) {
	n = N;
    for(int i=2; i<=n; i++) {
        int nw = get_cmp(1, i) - ask(1, i);
        while(nw--) {
            int l=1, r=i-1, p=i-1;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(get_cmp(mid, i) != ask(mid, i)) p = mid, l = mid + 1;
                else r = mid - 1;
            }
            edge[i][p] = edge[p][i] = 1;
            g[p].push_back(i);
            g[i].push_back(p);
        }
    }

    for(int i=1; i<=n; i++) {
        if(g[i].size() == 1) {
            dfs(i);
            Answer(ans);
            return ;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...