oj.uz

답안 #469612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469612 2021-09-01T12:41:58 Z aZvezda 도서관 (JOI18_library) C++14
0 / 100
 60 ms 296 KB 
#include <cstdio>
#include <vector>
#include "library.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 1e3 + 10;
set<int> lft;
bool used[MAX_N];

vector<int> load(int cnt, int n) {
    vector<int> ret(n, 0);
    for(auto it : lft) {
        if(cnt <= 0) {break;}
        cnt --;
        ret[it - 1] = 1;
    }
    return ret;
}

int getm(int m) {
    for(auto it : lft) {
        m --;
        if(m <= 0) {
            return it;
        }
    }
    return -1;
}

void Solve(int n) {
    vector<int> ans;

    for(int i = 1; i <= n; i ++) {
        lft.insert(i);
    }

    lft.erase(1);

    int l = 0, r = lft.size();
    while(l < r - 1) {
        int m = (l + r) / 2ll;

        auto quer = load(m, n);

        auto ans1 = Query(quer);
        quer[0] = 1;
        auto ans2 = Query(quer);

        if(ans1 < ans2) {
            l = m;
        } else {
            r = m;
        }
    }

    int now = getm(r);
    vector<int> ret = {1, now};
    lft.erase(now);

    while(ret.size() < n) {
        auto curr = ret.back();

        int l = 0, r = lft.size();
        while(l < r - 1) {
            int m = (l + r) / 2ll;

            auto quer = load(m, n);

            auto ans1 = Query(quer);
            quer[curr - 1] = 1;
            auto ans2 = Query(quer);

            if(ans1 < ans2) {
                l = m;
            } else {
                r = m;
            }
        }

        auto quer = load(r, n);

        auto ans1 = Query(quer);
        quer[curr - 1] = 1;
        auto ans2 = Query(quer);

        if(ans1 < ans2) {
            break;
        } else {
            int now = getm(r);
            ret.push_back(now);
            lft.erase(now);
        }
    }

    reverse(ret.begin(), ret.end());

    while(ret.size() < n) {
        auto curr = ret.back();

        int l = 0, r = lft.size();
        while(l < r - 1) {
            int m = (l + r) / 2ll;

            auto quer = load(m, n);

            auto ans1 = Query(quer);
            quer[curr - 1] = 1;
            auto ans2 = Query(quer);

            if(ans1 < ans2) {
                l = m;
            } else {
                r = m;
            }
        }

        auto quer = load(r, n);

        auto ans1 = Query(quer);
        quer[curr - 1] = 1;
        auto ans2 = Query(quer);

        if(ans1 < ans2) {
            break;
        } else {
            int now = getm(r);
            ret.push_back(now);
            lft.erase(now);
        }
    }

    Answer(ret);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     while(ret.size() < n) {
      |           ~~~~~~~~~~~^~~
library.cpp:109:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     while(ret.size() < n) {
      |           ~~~~~~~~~~~^~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 200 KB # of queries: 2776
2 Correct 54 ms 296 KB # of queries: 2780
3 Correct 48 ms 200 KB # of queries: 2924
4 Correct 59 ms 200 KB # of queries: 2922
5 Correct 55 ms 200 KB # of queries: 2906
6 Correct 60 ms 200 KB # of queries: 2912
7 Correct 48 ms 200 KB # of queries: 2914
8 Correct 41 ms 200 KB # of queries: 2802
9 Correct 32 ms 200 KB # of queries: 2906
10 Correct 30 ms 200 KB # of queries: 1728
11 Incorrect 0 ms 200 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 200 KB # of queries: 2776
2 Correct 54 ms 296 KB # of queries: 2780
3 Correct 48 ms 200 KB # of queries: 2924
4 Correct 59 ms 200 KB # of queries: 2922
5 Correct 55 ms 200 KB # of queries: 2906
6 Correct 60 ms 200 KB # of queries: 2912
7 Correct 48 ms 200 KB # of queries: 2914
8 Correct 41 ms 200 KB # of queries: 2802
9 Correct 32 ms 200 KB # of queries: 2906
10 Correct 30 ms 200 KB # of queries: 1728
11 Incorrect 0 ms 200 KB Wrong Answer [4]
12 Halted 0 ms 0 KB -