oj.uz

답안 #336719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336719 2020-12-16T14:08:57 Z mehrdad_sohrabi 도서관 (JOI18_library) C++14
100 / 100
 401 ms 752 KB 
#include <bits/stdc++.h>
#include "library.h"
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
/*
ll Query(vector <int> m){
    for (int i=0;i<m.size();i++){
        cout << m[i] << " ";
    }
    cout << endl;
    ll x;
    cin >> x;
    return x;
}
ll Answer(vector <int> ans){
    for (int i=0;i<ans.size();i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}
*/
ll cnt=0;
ll ask(vector <int> a,ll x,ll n){
    cnt++;
    if (cnt==2e4-1) cout << 1/0;
    vector <int> m;
    for (int i=0;i<n;i++){
        m.pb(0);
    }
    for (auto u : a){
        m[u-1]=1;
    }
    if (x!=0)
        m[x-1]=1;
    return Query(m);
}
ll what(ll x,ll y,ll n){
    cnt++;
    if (cnt==2e4-1) cout << 1/0;
    vector <int> m;
    for (int i=0;i<n;i++){
        m.pb(0);
    }
    m[y-1]=1;
    m[x-1]=1;
    return Query(m);
}

void Solve(ll n){
    if (n==1){
        vector <int> a;
        a.pb(1);
        Answer(a);
        return ;
    }
    ll x=1;
    vector <int> e;
    e.pb(1);
    while(true){
        vector <int> m;
        for (int i=1;i<=n;i++){
            m.pb(1);
        }
        for (auto u : e){
            m[u-1]=0;
        }
        ll cnt=Query(m);
        vector <int> w;
        for (int i=0;i<n;i++){
            if (m[i]==1) w.pb(i+1);
        }
        m[e.back()-1]=1;
        ll cnt2=Query(m);
        if (cnt2>cnt) break;
     //   cout << w.size() << endl;
       // for (auto u : w){
         //   cout << u << " jrnf" << endl;
        //}
        while(w.size()>1){
          //  cout << w.size() << " eiurhgier " << endl;
            vector <int> l;
            for (int i=0;i<w.size()/2;i++){
                l.pb(w[i]);
            }
            ll cnt=ask(l,e.back(),n);
            ll cnt2=ask(l,0,n);
            if (cnt>cnt2){
                vector <int> r;
                for (int i=w.size()/2;i<w.size();i++){
                    r.pb(w[i]);
                }
                w=r;
            }
            else{
                w=l;
            }
        }
        e.pb(w[0]);
        if (e.size()==n){
            Answer(e);
            return ;
        }
    }
   // cout << "KIR" << endl;
    reverse(e.begin(),e.end());
    while(true){
        vector <int> m;
        for (int i=1;i<=n;i++){
            m.pb(1);
        }
        for (auto u : e){
            m[u-1]=0;
        }
        ll cnt=Query(m);
        vector <int> w;
        for (int i=0;i<n;i++){
            if (m[i]==1) w.pb(i+1);
        }
        m[e.back()-1]=1;
        ll cnt2=Query(m);
        if (cnt2>cnt) break;
        while(w.size()>1){
            vector <int> l;
            for (int i=0;i<w.size()/2;i++){
                l.pb(w[i]);
            }
            ll cnt=ask(l,e.back(),n);
            ll cnt2=ask(l,0,n);
            if (cnt>cnt2){
                vector <int> r;
                for (int i=w.size()/2;i<w.size();i++){
                    r.pb(w[i]);
                }
                w=r;
            }
            else{
                w=l;
            }
        }
        e.pb(w[0]);
        if (e.size()==n){
            Answer(e);
            return ;
        }
    }
    Answer(e);
}
/*
int32_t main(){
    ll n;
    cin >> n;
    Solve(n);
}
*/

Compilation message

library.cpp: In function 'll ask(std::vector<int>, ll, ll)':
library.cpp:35:30: warning: division by zero [-Wdiv-by-zero]
   35 |     if (cnt==2e4-1) cout << 1/0;
      |                             ~^~
library.cpp: In function 'll what(ll, ll, ll)':
library.cpp:49:30: warning: division by zero [-Wdiv-by-zero]
   49 |     if (cnt==2e4-1) cout << 1/0;
      |                             ~^~
library.cpp: In function 'void Solve(ll)':
library.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int i=0;i<w.size()/2;i++){
      |                          ~^~~~~~~~~~~
library.cpp:99:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 for (int i=w.size()/2;i<w.size();i++){
      |                                       ~^~~~~~~~~
library.cpp:109:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  109 |         if (e.size()==n){
      |             ~~~~~~~~^~~
library.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for (int i=0;i<w.size()/2;i++){
      |                          ~^~~~~~~~~~~
library.cpp:141:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                 for (int i=w.size()/2;i<w.size();i++){
      |                                       ~^~~~~~~~~
library.cpp:151:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  151 |         if (e.size()==n){
      |             ~~~~~~~~^~~
library.cpp:66:8: warning: unused variable 'x' [-Wunused-variable]
   66 |     ll x=1;
      |        ^

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 380 KB # of queries: 2764
2 Correct 35 ms 492 KB # of queries: 2766
3 Correct 50 ms 364 KB # of queries: 2912
4 Correct 44 ms 364 KB # of queries: 2908
5 Correct 44 ms 364 KB # of queries: 2894
6 Correct 37 ms 384 KB # of queries: 2898
7 Correct 47 ms 364 KB # of queries: 2902
8 Correct 45 ms 364 KB # of queries: 2792
9 Correct 46 ms 364 KB # of queries: 2892
10 Correct 32 ms 364 KB # of queries: 1718
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 8
14 Correct 1 ms 380 KB # of queries: 12
15 Correct 3 ms 384 KB # of queries: 104
16 Correct 4 ms 364 KB # of queries: 234

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 380 KB # of queries: 2764
2 Correct 35 ms 492 KB # of queries: 2766
3 Correct 50 ms 364 KB # of queries: 2912
4 Correct 44 ms 364 KB # of queries: 2908
5 Correct 44 ms 364 KB # of queries: 2894
6 Correct 37 ms 384 KB # of queries: 2898
7 Correct 47 ms 364 KB # of queries: 2902
8 Correct 45 ms 364 KB # of queries: 2792
9 Correct 46 ms 364 KB # of queries: 2892
10 Correct 32 ms 364 KB # of queries: 1718
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 8
14 Correct 1 ms 380 KB # of queries: 12
15 Correct 3 ms 384 KB # of queries: 104
16 Correct 4 ms 364 KB # of queries: 234
17 Correct 387 ms 492 KB # of queries: 19150
18 Correct 376 ms 624 KB # of queries: 18950
19 Correct 389 ms 496 KB # of queries: 19136
20 Correct 328 ms 752 KB # of queries: 17876
21 Correct 330 ms 668 KB # of queries: 16804
22 Correct 377 ms 364 KB # of queries: 19192
23 Correct 379 ms 364 KB # of queries: 19132
24 Correct 149 ms 364 KB # of queries: 8872
25 Correct 396 ms 620 KB # of queries: 18706
26 Correct 324 ms 528 KB # of queries: 17434
27 Correct 167 ms 364 KB # of queries: 8782
28 Correct 335 ms 512 KB # of queries: 17954
29 Correct 401 ms 364 KB # of queries: 17934
30 Correct 399 ms 492 KB # of queries: 17954