oj.uz

Submission #58246

# Submission time Handle Problem Language Result Execution time Memory
58246 2018-07-17T08:57:03 Z King Suryal(#1687) Library (JOI18_library) C++11
100 / 100
 604 ms 576 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 39 ms 376 KB Output is correct
2 Correct 28 ms 376 KB Output is correct
3 Correct 32 ms 492 KB Output is correct
4 Correct 45 ms 492 KB Output is correct
5 Correct 53 ms 492 KB Output is correct
6 Correct 37 ms 492 KB Output is correct
7 Correct 42 ms 492 KB Output is correct
8 Correct 53 ms 492 KB Output is correct
9 Correct 50 ms 524 KB Output is correct
10 Correct 20 ms 524 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 3 ms 548 KB Output is correct
13 Correct 3 ms 548 KB Output is correct
14 Correct 2 ms 548 KB Output is correct
15 Correct 3 ms 548 KB Output is correct
16 Correct 5 ms 548 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 376 KB Output is correct
2 Correct 28 ms 376 KB Output is correct
3 Correct 32 ms 492 KB Output is correct
4 Correct 45 ms 492 KB Output is correct
5 Correct 53 ms 492 KB Output is correct
6 Correct 37 ms 492 KB Output is correct
7 Correct 42 ms 492 KB Output is correct
8 Correct 53 ms 492 KB Output is correct
9 Correct 50 ms 524 KB Output is correct
10 Correct 20 ms 524 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 3 ms 548 KB Output is correct
13 Correct 3 ms 548 KB Output is correct
14 Correct 2 ms 548 KB Output is correct
15 Correct 3 ms 548 KB Output is correct
16 Correct 5 ms 548 KB Output is correct
17 Correct 540 ms 572 KB Output is correct
18 Correct 557 ms 572 KB Output is correct
19 Correct 478 ms 572 KB Output is correct
20 Correct 455 ms 572 KB Output is correct
21 Correct 467 ms 572 KB Output is correct
22 Correct 510 ms 576 KB Output is correct
23 Correct 502 ms 576 KB Output is correct
24 Correct 146 ms 576 KB Output is correct
25 Correct 429 ms 576 KB Output is correct
26 Correct 463 ms 576 KB Output is correct
27 Correct 183 ms 576 KB Output is correct
28 Correct 604 ms 576 KB Output is correct
29 Correct 587 ms 576 KB Output is correct
30 Correct 542 ms 576 KB Output is correct