oj.uz

Submission #204807

# Submission time Handle Problem Language Result Execution time Memory
204807 2020-02-27T08:19:54 Z egekabas Library (JOI18_library) C++14
100 / 100
 345 ms 376 KB 
#include <bits/stdc++.h>
#include "library.h"
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n1;
int q(vector<int> v){
    if(v.size() == 1)
        return 1;
    vector<int> mpp(n1);
    for(auto u : v)
        mpp[u-1] = 1;
    return Query(mpp);
}
vector<vector<int>> div(vector<int> v){
    if(v.empty())
        return vector<vector<int>>();
    vector<int> v2;
    vector<int> newv;
    for(auto u : v){
        v2.pb(u);
        if(q(v2) == v2.size())
            continue;
        newv.pb(u);
        v2.pop_back();
    }
    vector<vector<int>> ret = div(newv);
    sort(v2.begin(), v2.end());
    ret.pb(v2);
    return ret;
}
int binsearch(int val, vector<int> v){
    int l = 0, r = v.size()-1;
    while(l < r){
        int m = (l+r)/2;
        vector<int> tmp;
        for(int i = 0; i <= m; ++i)
            tmp.pb(v[i]);
        tmp.pb(val);
        if(q(tmp) == tmp.size())
            l = m+1;
        else
            r = m;
    }
    return v[l];
}
void Solve(int n){
    n1 = n;
    if(n == 1){
        Answer({1});return;
    }
    if(n == 2){
        Answer({1, 2});return;
    }
    vector<int> v;
    for(int i = 1; i <= n; ++i)
        v.pb(i);
    vector<vector<int>> divi = div(v);
    vector<int> ans;
    int cur = 0;
    for(int i = 1; i <= n; ++i){
        vector<int> tmp;
        for(int j = 1; j <= n; ++j)
            if(i != j)
                tmp.pb(j);
        if(q(tmp) == 1){
            cur = i;
            break;
        }
    }
    ans.pb(cur);
    int cnt = 0;
    while(ans.size() < n){
        for(auto &u : divi){
            auto it = lower_bound(u.begin(), u.end(), cur);
            if(*it == cur){
                u.erase(it);
                break;
            }
        }
        for(auto v : divi){
            v.pb(cur);
            if(q(v) == v.size()) continue;
            v.pop_back();
            cur = binsearch(cur, v);
            ans.pb(cur);
            break;
        }
    }
    
    Answer(ans);
}

Compilation message

library.cpp: In function 'std::vector<std::vector<int> > div(std::vector<int>)':
library.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q(v2) == v2.size())
            ~~~~~~^~~~~~~~~~~~
library.cpp: In function 'int binsearch(int, std::vector<int>)':
library.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q(tmp) == tmp.size())
            ~~~~~~~^~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ans.size() < n){
           ~~~~~~~~~~~^~~
library.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q(v) == v.size()) continue;
                ~~~~~^~~~~~~~~~~
library.cpp:81:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 248 KB # of queries: 1707
2 Correct 35 ms 376 KB # of queries: 1745
3 Correct 39 ms 248 KB # of queries: 1897
4 Correct 33 ms 248 KB # of queries: 1850
5 Correct 35 ms 252 KB # of queries: 1772
6 Correct 36 ms 248 KB # of queries: 1811
7 Correct 36 ms 248 KB # of queries: 1808
8 Correct 33 ms 376 KB # of queries: 1716
9 Correct 35 ms 248 KB # of queries: 1808
10 Correct 17 ms 248 KB # of queries: 1096
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 376 KB # of queries: 0
13 Correct 5 ms 248 KB # of queries: 8
14 Correct 5 ms 248 KB # of queries: 10
15 Correct 7 ms 248 KB # of queries: 69
16 Correct 6 ms 248 KB # of queries: 164

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 248 KB # of queries: 1707
2 Correct 35 ms 376 KB # of queries: 1745
3 Correct 39 ms 248 KB # of queries: 1897
4 Correct 33 ms 248 KB # of queries: 1850
5 Correct 35 ms 252 KB # of queries: 1772
6 Correct 36 ms 248 KB # of queries: 1811
7 Correct 36 ms 248 KB # of queries: 1808
8 Correct 33 ms 376 KB # of queries: 1716
9 Correct 35 ms 248 KB # of queries: 1808
10 Correct 17 ms 248 KB # of queries: 1096
11 Correct 5 ms 248 KB # of queries: 0
12 Correct 5 ms 376 KB # of queries: 0
13 Correct 5 ms 248 KB # of queries: 8
14 Correct 5 ms 248 KB # of queries: 10
15 Correct 7 ms 248 KB # of queries: 69
16 Correct 6 ms 248 KB # of queries: 164
17 Correct 345 ms 376 KB # of queries: 12001
18 Correct 297 ms 248 KB # of queries: 11285
19 Correct 323 ms 248 KB # of queries: 11429
20 Correct 298 ms 376 KB # of queries: 10693
21 Correct 274 ms 252 KB # of queries: 10109
22 Correct 337 ms 348 KB # of queries: 11612
23 Correct 322 ms 376 KB # of queries: 11208
24 Correct 113 ms 248 KB # of queries: 5310
25 Correct 319 ms 376 KB # of queries: 11264
26 Correct 292 ms 376 KB # of queries: 10530
27 Correct 122 ms 248 KB # of queries: 5437
28 Correct 299 ms 248 KB # of queries: 10966
29 Correct 295 ms 248 KB # of queries: 10953
30 Correct 300 ms 248 KB # of queries: 10966