oj.uz

답안 #58243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58243 2018-07-17T08:52:24 Z King Suryal(#1687) 도서관 (JOI18_library) C++11
0 / 100
 41 ms 376 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[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
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 376 KB Wrong Answer [8]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 376 KB Wrong Answer [8]
2 Halted 0 ms 0 KB -