oj.uz

Submission #204802

# Submission time Handle Problem Language Result Execution time Memory
204802 2020-02-27T08:12:56 Z egekabas Library (JOI18_library) C++14
0 / 100
 349 ms 504 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;
    if(v.empty())
        return 0;
    vector<int> mpp(n1, 0);
    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;
    vector<int> v;
    for(int i = 1; i <= n; ++i)
        v.pb(i);
    vector<vector<int>> divi = div(v);
    auto it = divi.begin();
    while(it < divi.end()){
        if((*it).empty())
            it = divi.erase(it);
        else
            ++it;
    }
    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:33: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:51: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:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ans.size() < n){
           ~~~~~~~~~~~^~~
library.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q(v) == v.size()) continue;
                ~~~~~^~~~~~~~~~~
library.cpp:84:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 320 KB # of queries: 1707
2 Correct 30 ms 248 KB # of queries: 1745
3 Correct 35 ms 248 KB # of queries: 1897
4 Correct 36 ms 376 KB # of queries: 1850
5 Correct 36 ms 248 KB # of queries: 1772
6 Correct 26 ms 328 KB # of queries: 1811
7 Correct 36 ms 328 KB # of queries: 1808
8 Correct 37 ms 376 KB # of queries: 1716
9 Correct 32 ms 376 KB # of queries: 1808
10 Correct 22 ms 376 KB # of queries: 1096
11 Incorrect 5 ms 376 KB Wrong Answer [5]
12 Correct 5 ms 380 KB # of queries: 2
13 Correct 5 ms 376 KB # of queries: 8
14 Correct 5 ms 376 KB # of queries: 10
15 Correct 6 ms 248 KB # of queries: 69
16 Correct 7 ms 248 KB # of queries: 164

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 320 KB # of queries: 1707
2 Correct 30 ms 248 KB # of queries: 1745
3 Correct 35 ms 248 KB # of queries: 1897
4 Correct 36 ms 376 KB # of queries: 1850
5 Correct 36 ms 248 KB # of queries: 1772
6 Correct 26 ms 328 KB # of queries: 1811
7 Correct 36 ms 328 KB # of queries: 1808
8 Correct 37 ms 376 KB # of queries: 1716
9 Correct 32 ms 376 KB # of queries: 1808
10 Correct 22 ms 376 KB # of queries: 1096
11 Incorrect 5 ms 376 KB Wrong Answer [5]
12 Correct 5 ms 380 KB # of queries: 2
13 Correct 5 ms 376 KB # of queries: 8
14 Correct 5 ms 376 KB # of queries: 10
15 Correct 6 ms 248 KB # of queries: 69
16 Correct 7 ms 248 KB # of queries: 164
17 Correct 349 ms 504 KB # of queries: 12001
18 Correct 323 ms 376 KB # of queries: 11285
19 Correct 315 ms 376 KB # of queries: 11429
20 Correct 295 ms 376 KB # of queries: 10693
21 Correct 273 ms 252 KB # of queries: 10109
22 Correct 329 ms 376 KB # of queries: 11612
23 Correct 309 ms 332 KB # of queries: 11208
24 Correct 113 ms 332 KB # of queries: 5310
25 Correct 312 ms 248 KB # of queries: 11264
26 Correct 288 ms 376 KB # of queries: 10530
27 Correct 122 ms 248 KB # of queries: 5437
28 Correct 285 ms 376 KB # of queries: 10966
29 Correct 310 ms 248 KB # of queries: 10953
30 Correct 294 ms 248 KB # of queries: 10966