oj.uz

Submission #469620

# Submission time Handle Problem Language Result Execution time Memory
469620 2021-09-01T13:08:28 Z aZvezda Library (JOI18_library) C++14
100 / 100
 629 ms 460 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;

    lft.clear();

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

    lft.erase(1);
    vector<int> ret = {1};

    for(int iter = 0; iter < 2; iter ++) {
        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());
    }

    Answer(ret);
}

Compilation message

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

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 200 KB # of queries: 2778
2 Correct 51 ms 200 KB # of queries: 2782
3 Correct 48 ms 200 KB # of queries: 2926
4 Correct 62 ms 200 KB # of queries: 2924
5 Correct 35 ms 200 KB # of queries: 2908
6 Correct 48 ms 200 KB # of queries: 2914
7 Correct 50 ms 200 KB # of queries: 2916
8 Correct 51 ms 200 KB # of queries: 2804
9 Correct 45 ms 200 KB # of queries: 2908
10 Correct 33 ms 200 KB # of queries: 1730
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 0 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 12
15 Correct 2 ms 200 KB # of queries: 104
16 Correct 4 ms 200 KB # of queries: 240

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 200 KB # of queries: 2778
2 Correct 51 ms 200 KB # of queries: 2782
3 Correct 48 ms 200 KB # of queries: 2926
4 Correct 62 ms 200 KB # of queries: 2924
5 Correct 35 ms 200 KB # of queries: 2908
6 Correct 48 ms 200 KB # of queries: 2914
7 Correct 50 ms 200 KB # of queries: 2916
8 Correct 51 ms 200 KB # of queries: 2804
9 Correct 45 ms 200 KB # of queries: 2908
10 Correct 33 ms 200 KB # of queries: 1730
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 0 ms 200 KB # of queries: 8
14 Correct 1 ms 200 KB # of queries: 12
15 Correct 2 ms 200 KB # of queries: 104
16 Correct 4 ms 200 KB # of queries: 240
17 Correct 612 ms 452 KB # of queries: 19170
18 Correct 595 ms 328 KB # of queries: 18968
19 Correct 622 ms 328 KB # of queries: 19148
20 Correct 482 ms 452 KB # of queries: 17888
21 Correct 479 ms 328 KB # of queries: 16824
22 Correct 576 ms 452 KB # of queries: 19212
23 Correct 629 ms 460 KB # of queries: 19146
24 Correct 223 ms 300 KB # of queries: 8882
25 Correct 602 ms 452 KB # of queries: 18718
26 Correct 534 ms 448 KB # of queries: 17454
27 Correct 181 ms 320 KB # of queries: 8798
28 Correct 533 ms 328 KB # of queries: 17954
29 Correct 516 ms 328 KB # of queries: 17934
30 Correct 522 ms 328 KB # of queries: 17954