Submission #1301897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301897		hg-2008	Library (JOI18_library)	C++20	0 / 100	50 ms	424 KiB

library

#include "library.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define all(x) x.begin(), x.end()
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0)
#define endl '\n'
#define pb push_back
#define out(x) {cout << x << '\n'; return;}
#define ff first
#define ss second
#define sz(x) (int)(x).size()
//Query(M)
//Answer(res)
void Solve(int n){
    vector<int> b(n);
    vector<int> ans(n);
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= n ; j++) b[j-1] = (i != j);
        if (Query(b) == 1){
            ans[0] = i;
            break;
        }
    }
    vector<int> rm;
    for (int i = 1 ; i <= n ; i++) if (i != ans[0]) rm.pb(i);
    if (n <= 200){
        for (int i = 1 ; i < n ; i++){
            for (int j = 0 ; j < n ; j++) b[j] = 0;
            b[ans[i-1]-1] = 1;
            for (auto x : rm){
                b[x-1] = 1;
                if (Query(b) == 1){
                    ans[i] = x;
                    break;
                }
                b[x-1] = 0;
            }
            b[ans[i-1]-1] = 0;
            vector<int> nrm = rm; rm.clear();
            for (auto x : nrm) if (ans[i] != x) rm.pb(x);
        }
        Answer(ans);
        return;
    }
    for (int i = 1 ; i < n ; i++){
        for (int j = 0 ; j < n ; j++) b[j] = 0;
        b[ans[i-1]-1] = 1;
        int l = -1, r = sz(rm)+1, mid;
        while (r-l > 1){
            mid = (l+r)/2;
            for (int j = 0 ; j <= mid ; j++) b[rm[j]-1] = 1;
            int x = Query(b);
            b[ans[i-1]-1] = 0;
            int y = Query(b);
            if (x - y == 0) r = mid;
            else l = mid;
            for (int j = 0 ; j <= mid ; j++) b[rm[j]-1] = 0;
            b[ans[i-1]-1] = 1;
        }
        ans[i] = rm[r];
        vector<int> nrm = rm; rm.clear();
        for (auto x : nrm) if (ans[i] != x) rm.pb(x);
    }
    Answer(ans);
}

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