oj.uz

Submission #242739

# Submission time Handle Problem Language Result Execution time Memory
242739 2020-06-29T08:10:41 Z osaaateiasavtnl Library (JOI18_library) C++17
100 / 100
 501 ms 504 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 376 KB # of queries: 2387
2 Correct 41 ms 484 KB # of queries: 2433
3 Correct 55 ms 384 KB # of queries: 2638
4 Correct 51 ms 376 KB # of queries: 2593
5 Correct 54 ms 384 KB # of queries: 2504
6 Correct 49 ms 376 KB # of queries: 2553
7 Correct 49 ms 376 KB # of queries: 2568
8 Correct 43 ms 256 KB # of queries: 2402
9 Correct 51 ms 480 KB # of queries: 2512
10 Correct 26 ms 384 KB # of queries: 1478
11 Correct 5 ms 256 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 432 KB # of queries: 7
15 Correct 5 ms 380 KB # of queries: 73
16 Correct 6 ms 380 KB # of queries: 187

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 376 KB # of queries: 2387
2 Correct 41 ms 484 KB # of queries: 2433
3 Correct 55 ms 384 KB # of queries: 2638
4 Correct 51 ms 376 KB # of queries: 2593
5 Correct 54 ms 384 KB # of queries: 2504
6 Correct 49 ms 376 KB # of queries: 2553
7 Correct 49 ms 376 KB # of queries: 2568
8 Correct 43 ms 256 KB # of queries: 2402
9 Correct 51 ms 480 KB # of queries: 2512
10 Correct 26 ms 384 KB # of queries: 1478
11 Correct 5 ms 256 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 432 KB # of queries: 7
15 Correct 5 ms 380 KB # of queries: 73
16 Correct 6 ms 380 KB # of queries: 187
17 Correct 469 ms 504 KB # of queries: 18008
18 Correct 501 ms 384 KB # of queries: 17231
19 Correct 466 ms 388 KB # of queries: 17451
20 Correct 390 ms 384 KB # of queries: 16277
21 Correct 364 ms 388 KB # of queries: 15362
22 Correct 489 ms 504 KB # of queries: 17617
23 Correct 487 ms 504 KB # of queries: 17170
24 Correct 149 ms 384 KB # of queries: 7885
25 Correct 475 ms 388 KB # of queries: 17118
26 Correct 479 ms 424 KB # of queries: 15989
27 Correct 159 ms 384 KB # of queries: 7994
28 Correct 489 ms 388 KB # of queries: 17935
29 Correct 477 ms 504 KB # of queries: 17915
30 Correct 437 ms 504 KB # of queries: 17935