Submission #242739

#	Time	Username	Problem	Language	Result	Execution time	Memory
242739		osaaateiasavtnl	도서관 (JOI18_library)	C++17	100 / 100	501 ms	504 KiB

library

#include <bits/stdc++.h>
using namespace std; 
mt19937 rnd(228);
vector <int> ans, pos;
int N;
#ifdef HOME
int Q = 0;
int Query(vector <int> m) { 
    if (m.size() == 1) return 1;
    ++Q;
    vector <bool> used(N);
    for (int i = 0; i < N; ++i) {
        if (m[i]) used[pos[i]] = 1;
    }   
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += used[i] && (!i || !used[i - 1]);
    }   
    return ans;
}
void Answer(vector <int> a) { 
    cout << "Q = " << Q << '\n';
    auto b = a; reverse(b.begin(), b.end());
    if (a == ans || b == ans) cout << "correct\n";
    else {
        for (int e : ans) cout << e << ' '; cout << '\n';
        for (int e : a) cout << e << ' '; cout << '\n';
        cout << "WA\n";
        exit(0);
    }
}
#else
#include "library.h"
#endif
 
#define ii pair <int, int>
#define app push_back
// Query()
// Answer()
void Solve(int n) {
    #ifdef HOME
    Q = 0;
    #endif
    N = n;

    if (n == 1) {
        vector <int> ans = {1};
        Answer(ans);
        return;
    }   

    int S = -1;
    for (int i = 1; i <= n; ++i) {
        vector <int> q(N);
        for (int j = 1; j <= n; ++j)
            if (j != i)
                q[j-1] = 1;
        if (Query(q) == 1) {
            S = i;
            break;            
        }
    }   

    vector <int> ans = {S};
    vector <bool> used(n+1);
    used[S] = 1;
    while (ans.size() < n) {
        vector <int> cand;
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                cand.app(i);                
            }   
        }   

        int l = 0, r = cand.size() - 1;
        while (l < r) {
            int m = (l + r) >> 1;

            vector <int> q(N);
            for (int i = l; i <= m; ++i)
                q[cand[i]-1] = 1;                    

            int res1 = Query(q);
            q[ans.back()-1] = 1;
            int res2 = Query(q);
            if (res2 == res1) {
                r = m;
            }   
            else {
                l = m+1;
            }
        }   

        ans.app(cand[l]);
        used[cand[l]] = 1;
    }

    for (auto e : ans)
        cerr << e << ' ';
    cout << endl;            
    
    Answer(ans);
}
#ifdef HOME 
int main() {
    int t = 10;
    while (t--) {
        int N = 1000;
        ans.clear();
        pos.resize(N);
        for (int i = 1; i <= N; ++i) ans.app(i);
        shuffle(ans.begin(), ans.end(), rnd);
        for (int i = 0; i < N; ++i) pos[ans[i] - 1] = i;
        Solve(N);
    }
}
#endif

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ans.size() < n) {
            ~~~~~~~~~~~^~~

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