oj.uz

Submission #80716

# Submission time Handle Problem Language Result Execution time Memory
80716 2018-10-22T04:29:24 Z admin Library (JOI18_library) C++17
100 / 100
 388 ms 592 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
 
int n;
vector<int> res;
vector<int> arr;
 
int countLeftLast(int s, int e) {
    vector<int> q(n, 0);
    for (int i = s; i <= e; ++i) {
        q[arr[i]] ^= 1;
    }
    int l = (e - s + 1) - Query(q);
    for (int i = 0; i < arr.size(); ++i) {
        q[arr[i]] ^= 1;
    }
    int r = (arr.size() - (e - s + 1)) - Query(q);
    int c = (l << 1) + (arr.size() - l - r - 1);
    return ((e - s + 1) << 1) - c;
}
 
vector<int> findLast(int x, int y, int c) {
    if (c == 0) return vector<int>();
    if (y - x + 1 == c) {
        vector<int> ret;
        for (int i = x; i <= y; ++i) ret.push_back(i);
        return ret;
    }
    int m = (x + y) / 2;
    int l = countLeftLast(x, m);
    vector<int> ret;
    vector<int> lv = findLast(x, m, l);
    vector<int> rv = findLast(m + 1, y, c - l);
    for (int i : lv) ret.push_back(i);
    for (int i : rv) ret.push_back(i);
    return ret;
}
 
void Solve(int N) {
    n = N;
    res.resize(n, 0);
    arr.resize(n, 0);
    for (int i = 0; i < n; ++i) arr[i] = i;
    int s = 0, e = n - 1;
    while (arr.size() > 1) {
        vector<int> ret = findLast(0, arr.size() - 1, 2);
        if (s > 0) {
            vector<int> q(n, 0);
            q[res[e + 1]] = 1;
            q[arr[ret[0]]] = 1;
            int x = Query(q);
            if (x < 2) swap(ret[0], ret[1]);
        }
        res[s] = arr[ret[0]];
        res[e] = arr[ret[1]];
        vector<int>::iterator it;
        for (it = arr.begin(); *it != res[s]; ++it);
        arr.erase(it);
        for (it = arr.begin(); *it != res[e]; ++it);
        arr.erase(it);
        ++s; --e;
    }
    if (arr.size()) res[s] = arr[0];
    for (int &i : res) ++i;
    Answer(res);
}

Compilation message

library.cpp: In function 'int countLeftLast(int, int)':
library.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < arr.size(); ++i) {
                     ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 248 KB # of queries: 2125
2 Correct 27 ms 324 KB # of queries: 2092
3 Correct 35 ms 528 KB # of queries: 2215
4 Correct 31 ms 528 KB # of queries: 2223
5 Correct 29 ms 528 KB # of queries: 2207
6 Correct 23 ms 528 KB # of queries: 2239
7 Correct 24 ms 528 KB # of queries: 2235
8 Correct 29 ms 552 KB # of queries: 2181
9 Correct 34 ms 576 KB # of queries: 2208
10 Correct 18 ms 576 KB # of queries: 1253
11 Correct 2 ms 576 KB # of queries: 0
12 Correct 2 ms 576 KB # of queries: 0
13 Correct 2 ms 576 KB # of queries: 4
14 Correct 2 ms 576 KB # of queries: 7
15 Correct 2 ms 576 KB # of queries: 76
16 Correct 4 ms 576 KB # of queries: 154

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 248 KB # of queries: 2125
2 Correct 27 ms 324 KB # of queries: 2092
3 Correct 35 ms 528 KB # of queries: 2215
4 Correct 31 ms 528 KB # of queries: 2223
5 Correct 29 ms 528 KB # of queries: 2207
6 Correct 23 ms 528 KB # of queries: 2239
7 Correct 24 ms 528 KB # of queries: 2235
8 Correct 29 ms 552 KB # of queries: 2181
9 Correct 34 ms 576 KB # of queries: 2208
10 Correct 18 ms 576 KB # of queries: 1253
11 Correct 2 ms 576 KB # of queries: 0
12 Correct 2 ms 576 KB # of queries: 0
13 Correct 2 ms 576 KB # of queries: 4
14 Correct 2 ms 576 KB # of queries: 7
15 Correct 2 ms 576 KB # of queries: 76
16 Correct 4 ms 576 KB # of queries: 154
17 Correct 350 ms 588 KB # of queries: 15725
18 Correct 341 ms 588 KB # of queries: 15577
19 Correct 321 ms 588 KB # of queries: 15687
20 Correct 326 ms 592 KB # of queries: 14648
21 Correct 314 ms 592 KB # of queries: 13757
22 Correct 362 ms 592 KB # of queries: 15713
23 Correct 369 ms 592 KB # of queries: 15826
24 Correct 135 ms 592 KB # of queries: 7101
25 Correct 348 ms 592 KB # of queries: 15274
26 Correct 321 ms 592 KB # of queries: 14236
27 Correct 103 ms 592 KB # of queries: 7058
28 Correct 382 ms 592 KB # of queries: 16471
29 Correct 388 ms 592 KB # of queries: 16454
30 Correct 372 ms 592 KB # of queries: 16471