oj.uz

Submission #336706

# Submission time Handle Problem Language Result Execution time Memory
336706 2020-12-16T12:55:53 Z mehrdad_sohrabi Library (JOI18_library) C++14
19 / 100
 422 ms 492 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 ask(vector <int> a,ll x,ll n){
    vector <int> m;
    for (int i=0;i<n;i++){
        m.pb(0);
    }
    for (auto u : a){
        m[u-1]=1;
    }
    m[x-1]=1;
    return Query(m);
}
ll what(ll x,ll y,ll n){
    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){
    vector <vector <int> > mol;
    ll cnt=1;
    vector <int> a;
    for (int i=1;i<=n;i++){
        a.pb(i);
    }
    random_shuffle(a.begin(),a.end());
    for (auto u : a){
        if (mol.size()==0){
            vector <int> t;
            t.pb(u);
            mol.pb(t);
            continue;
        }
        vector <int> t;
        for (auto z : mol){
            for (auto v : z){
                t.pb(v);
            }
        }
        ll w=ask(t,u,n);
//cout << cnt << " " << w << endl;
        if (w>cnt){
            cnt=w;
            vector <int> d;
            d.pb(u);
            mol.pb(d);
            continue;
        }
        vector <int> q;
        ll p1=0;
        vector <vector <int> > lom;
        for (int i=0;i<mol.size();i++){
            vector <int> v=mol[i];
            if (v.size()==0){
                cout << 1/0;
            }
            ll w=ask(v,u,n);
            if (w>1) {
                lom.pb(v);
                continue;
            }
            if (p1==0){
                if (what(mol[i].back(),u,n)==1){
                    q=mol[i];
                    q.pb(u);
                }
                else{
                    reverse(mol[i].begin(),mol[i].end());
                    q=mol[i];
                    q.pb(u);
                }
                p1=1;
            }
            else {
                p1=2;
                if (what(mol[i][0],u,n)==1){
                    for (auto z : mol[i]){
                        q.pb(z);
                    }
                }
                else{
                    reverse(mol[i].begin(),mol[i].end());
                    for (auto z : mol[i]){
                        q.pb(z);
                    }
                }
            }
            /*
            if (p1==2 || (p1==1 && cnt==w)) {
                for (int j=i+1;j<mol.size();j++){
                    lom.pb(mol[j]);
                }
                break;
            }
            */
        }
        cnt=w;
        mol=lom;
        mol.pb(q);
    }
    if (mol.size()>1){
   //     cout << "KIR KHAR" << endl;
    }
    Answer(mol[0]);
}
/*
int32_t main(){
    ll n;
    cin >> n;
    Solve(n);
}
*/

Compilation message

library.cpp: In function 'void Solve(ll)':
library.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i=0;i<mol.size();i++){
      |                      ~^~~~~~~~~~~
library.cpp:88:26: warning: division by zero [-Wdiv-by-zero]
   88 |                 cout << 1/0;
      |                         ~^~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 364 KB # of queries: 4944
2 Correct 85 ms 364 KB # of queries: 5247
3 Correct 61 ms 380 KB # of queries: 5310
4 Correct 72 ms 364 KB # of queries: 4995
5 Correct 79 ms 364 KB # of queries: 4757
6 Correct 60 ms 492 KB # of queries: 5060
7 Correct 81 ms 364 KB # of queries: 5338
8 Correct 75 ms 492 KB # of queries: 4842
9 Correct 85 ms 364 KB # of queries: 5293
10 Correct 34 ms 364 KB # of queries: 2270
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 3
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 1 ms 364 KB # of queries: 51
16 Correct 4 ms 364 KB # of queries: 154

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 364 KB # of queries: 4944
2 Correct 85 ms 364 KB # of queries: 5247
3 Correct 61 ms 380 KB # of queries: 5310
4 Correct 72 ms 364 KB # of queries: 4995
5 Correct 79 ms 364 KB # of queries: 4757
6 Correct 60 ms 492 KB # of queries: 5060
7 Correct 81 ms 364 KB # of queries: 5338
8 Correct 75 ms 492 KB # of queries: 4842
9 Correct 85 ms 364 KB # of queries: 5293
10 Correct 34 ms 364 KB # of queries: 2270
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 3
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 1 ms 364 KB # of queries: 51
16 Correct 4 ms 364 KB # of queries: 154
17 Runtime error 422 ms 492 KB Execution killed with signal 13 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -