Submission #80716

#	Time	Username	Problem	Language	Result	Execution time	Memory
80716		admin	Library (JOI18_library)	C++17	100 / 100	388 ms	592 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81