Submission #336719

#	Time	Username	Problem	Language	Result	Execution time	Memory
336719		mehrdad_sohrabi	Library (JOI18_library)	C++14	100 / 100	401 ms	752 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81