Submission #1207050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207050		VMaksimoski008	Library (JOI18_library)	C++20	100 / 100	516 ms	4404 KiB

library

#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);
        for(; nw>0; nw--) {
            int l=1, r=i-1, p=-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() < 2) {
            dfs(i);
            break;
        }
    }
    Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81