Submission #768606

#	Time	Username	Problem	Language	Result	Execution time	Memory
768606		raysh07	Library (JOI18_library)	C++17	0 / 100	49 ms	308 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

vector<vector<int>> adj;
vector<int> comp;

bool check(int i, int j, int n){
    if (i == j) return false;
    
    vector <int> m(n, 0);
    for (int k = i; k <= j; k++){
        m[k] = 1;
    }
    
    for (auto x : adj[i]) m[x] = 0;
    
    int a1 = Query(m);
    m[i] = 0;
    int a2 = Query(m);
    
    return a2 >= a1;
}

void dfs(int u, int par = -1){
    comp.push_back(u + 1);
    for (int v : adj[u]){
        if (v != par){
            dfs(v, u);
        }
    }
}

void Solve(int n)
{
// 	vector<int> M(N);

// 	for(int i = 0; i < N; i++) {
// 		M[i] = 1;
// 	}

// 	int A = Query(M);

// 	vector<int> res(N);

// 	for(int i = 0; i < N; i++) {
// 		res[i] = i + 1;
// 	}

// 	Answer(res);

    adj.resize(n);

    for (int i = 0; i < n; i++){
        while (check(i, n - 1, n)){
            int l = i + 1, r = n - 1;
            
            while (l != r){
                int m = (l + r)/2;
                
                if (check(i, m, n)) r = m;
                else l = m + 1;
            }
            
            adj[i].push_back(l);
            adj[l].push_back(i);
        }
    }
    
    for (int i = 0; i < n; i++){
        if (adj[i].size() == 1){
            dfs(i);
            break;
        }
    }
    
    Answer(comp);
}

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