oj.uz

Submission #387677

# Submission time Handle Problem Language Result Execution time Memory
387677 2021-04-09T05:42:12 Z i_am_noob Shopping (JOI21_shopping) C++17
1 / 100
 172 ms 23964 KB 
#include "Anna.h"
#include<bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

namespace {

int n,l,r,res;
int zck;
const int K=201;
vector<int> vec1,vec2;
vector<bool> tree1,tree2;
bool flag;

vector<int> build(vector<bool>& tree){
    vector<int> stk;
    vector<int> pre;
    int cur=0;
    for(auto i: tree){
        if(i){
            pre.pb(sz(stk)?stk.back():-1);
            stk.pb(cur);
            cur++;
        }
        else{
            stk.pop_back();
        }
    }
    return pre;
}

void response(vector<int> id, vector<int> pre, vector<int>& vec){
    int L,R;
    rep(sz(id)) if(id[i]>=l){
        L=i;
        break;
    }
    rep3(i,sz(id)-1,0) if(id[i]<=r){
        R=i;
        break;
    }
    if(sz(id)<100) for(auto i: id) bug(i);
    bug(L,R);
    vector<int> tmp1;
    rep(K) tmp1.pb(sz(id)/K);
    rep(sz(id)%K) tmp1[i]++;
    int lpos,rpos,cur=0,y;
    rep(K){
        if(tmp1[i]+cur>L){
            lpos=i;
            break;
        }
        cur+=tmp1[i];
    }
    cur=0;
    rep(K){
        if(tmp1[i]+cur>R){
            rpos=i;
            break;
        }
        cur+=tmp1[i];
    }
    if(rpos<=lpos+1){
        SendA(0);
        flag=0;
        int z=lpos;
        rep(8) SendA(z&1),z>>=1;
        cur=0;
        rep(lpos) cur+=tmp1[i];
        rep(tmp1[lpos]) vec.pb(id[cur+i]);
        if(lpos+1<n) rep(tmp1[lpos+1]) vec.pb(id[cur+tmp1[lpos]+i]);
        if(sz(vec)<100) for(auto i: vec) bug(i);
        return;
    }
    rep2(i,lpos+1,rpos) if(pre[i]<lpos+1) y=i;
    SendA(1);
    flag=1;
    int z=y;
    rep(8) SendA(z&1),z>>=1;
    cur=0;
    rep(pre[y]) cur+=tmp1[i];
    if(pre[y]>=0) rep(tmp1[pre[y]]) vec.pb(id[cur+i]);
    bug(pre[y],y);
    bug("A",sz(vec));
    vec.pb(-1);
    rep2(i,y+1,sz(pre)) if(pre[i]<y){
        bug(i);
        cur=0;
        rep1(j,i) cur+=tmp1[j];
        rep1(j,tmp1[i]) vec.pb(id[cur+j]);
        break;
    }
    bug("A",sz(vec));
}

}  // namespace

void InitA(int N, int L, int R) {
    n=N,l=L,r=R;
}

void ReceiveA(bool x) {
    if(!zck){
        static int cnt=2*K;
        tree1.pb(x);
        cnt--;
        if(cnt<=0){
            vector<int> tmp;
            rep(n) tmp.pb(i);
            vector<int> pre=build(tree1);
            response(tmp,pre,vec1);
            zck++;
        }
    }
    else if(zck==1){
        if(flag){
            static int cnt=20,pos=0;
            pos+=x*(1<<(20-cnt));
            cnt--;
            if(!cnt){
                for(auto& i: vec1) if(i==-1) i=pos;
                flag=0;
            }
        }
        else{
            static int cnt=2*K;
            tree2.pb(x);
            cnt--;
            if(cnt<=0){
                vector<int> pre=build(tree2);
                response(vec1,pre,vec2);
                bug(sz(vec1),sz(vec2));
                zck++;
            }
        }
    }
    else{
        if(flag){
            static int cnt=20,pos=0;
            pos+=x*(1<<(20-cnt));
            cnt--;
            if(!cnt){
                for(auto& i: vec2) if(i==-1) i=pos;
                flag=0;
            }
        }
        else{
            static int cnt=2*sz(vec2);
            tree2.pb(x);
            cnt--;
            if(cnt<=0){
                vector<int> pre=build(tree2);
                rep3(i,sz(vec2)-1,0) if(vec2[i]<=r&&(pre[i]==-1||vec2[pre[i]]<l)){
                    res=vec2[i];
                    break;
                }
            }
        }
    }
}

int Answer() {
    bug(res,sz(vec1),sz(vec2));
    return res;
}

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

namespace {

int n;
int zck;
bool flag;
vector<int> a,vec1,vec2,minvec;
const int K=201;

vector<bool> build(vector<int>& vec){
    vector<bool> res;
    vector<int> stk;
    for(auto i: vec){
        while(sz(stk)&&i<stk.back()) res.pb(0),stk.pop_back();
        res.pb(1),stk.pb(i);
    }
    rep(sz(stk)) res.pb(0);
    assert(sz(res)==2*sz(vec));
    return res;
}

vector<int> Get(vector<int>& id, int val){
    vector<int> tmp1;
    rep(K) tmp1.pb(sz(id)/K);
    rep(sz(id)%K) tmp1[i]++;
    int cur;
    vector<int> res;
    if(sz(id)<100) for(auto i: id) bug(i);
    if(flag){
        bug(sz(id));
        cur=0;
        rep(val) cur+=tmp1[i];
        int minn=n+1,minid;
        rep2(i,cur,cur+tmp1[val]) if(a[id[i]]<minn) minn=a[id[i]],minid=id[i];
        int z=minid;
        rep(20) SendB(z&1),z>>=1;
        rep3(i,val-1,0) if(minvec[i]<minvec[val]){
            cur=0;
            rep1(j,i) cur+=tmp1[j];
            rep2(j,cur,cur+tmp1[i]) res.pb(id[j]);
            bug(i);
            break;
        }
        bug("B",sz(res));
        res.pb(minid);
        bug(val);
        rep2(i,val+1,sz(minvec)) if(minvec[i]<minvec[val]){
            bug(i);
            cur=0;
            rep1(j,i) cur+=tmp1[j];
            rep2(j,cur,cur+tmp1[i]) res.pb(id[j]);
            break;
        }
        bug("B",sz(res));
    }
    else{
        cur=0;
        rep(val) cur+=tmp1[i];
        rep2(i,cur,cur+tmp1[val]) res.pb(id[i]);
        if(val+1<sz(tmp1)) rep2(i,cur+tmp1[val],cur+tmp1[val]+tmp1[val+1]) res.pb(id[i]);
        if(sz(res)<100) for(auto i: res) bug(i);
    }
    return res;
}

vector<bool> tree1,tree2;

}  // namespace



void InitB(int N, vector<int> A) {
    n=N,a=A;
    vector<int> tmp1;
    rep(K) tmp1.pb(n/K);
    rep(n%K) tmp1[i]++;
    int cur=0;
    rep(K){
        int minn=inf;
        rep2(j,cur,cur+tmp1[i]) minn=min(minn,a[j]);
        minvec.pb(minn);
        cur+=tmp1[i];
    }
    tree1=build(minvec);
    bug(sz(tree1));
    for(auto i: tree1) SendB(i);
}

void ReceiveB(bool y) {
    if(!zck){
        flag=y;
        zck++;
    }
    else if(zck==1){
        static int cnt=8,val=0;
        val+=y*(1<<(8-cnt));
        cnt--;
        if(!cnt){
            vector<int> tmp,tmp1;
            rep(n) tmp.pb(i);
            vec1=Get(tmp,val);
            rep(K) tmp1.pb(sz(vec1)/K);
            rep(sz(vec1)%K) tmp1[i]++;
            minvec.clear();
            int cur=0;
            rep(K){
                int minn=inf;
                rep2(j,cur,cur+tmp1[i]) minn=min(minn,a[j]);
                minvec.pb(minn);
                cur+=tmp1[i];
            }
            tree2=build(minvec);
            bug(sz(tree2));
            for(auto i: tree2) SendB(i);
            zck++;
        }
    }
    else if(zck==2){
        flag=y;
        zck++;
    }
    else{
        static int cnt=8,val=0;
        val+=y*(1<<(8-cnt));
        cnt--;
        if(!cnt){
            vec2=Get(vec1,val);
            minvec.clear();
            for(auto i: vec2) minvec.pb(a[i]);
            tree2=build(minvec);
            bug(sz(tree2),sz(vec1),sz(vec2));
            for(auto i: tree2) SendB(i);
            zck++;
        }
    }
}

Compilation message

Anna.cpp: In function 'void {anonymous}::response(std::vector<int>, std::vector<int>, std::vector<int>&)':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:65:36: note: in expansion of macro 'bug'
   65 |     if(sz(id)<100) for(auto i: id) bug(i);
      |                                    ^~~
Anna.cpp:65:29: warning: unused variable 'i' [-Wunused-variable]
   65 |     if(sz(id)<100) for(auto i: id) bug(i);
      |                             ^
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:66:5: note: in expansion of macro 'bug'
   66 |     bug(L,R);
      |     ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:95:42: note: in expansion of macro 'bug'
   95 |         if(sz(vec)<100) for(auto i: vec) bug(i);
      |                                          ^~~
Anna.cpp:95:34: warning: unused variable 'i' [-Wunused-variable]
   95 |         if(sz(vec)<100) for(auto i: vec) bug(i);
      |                                  ^
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:106:5: note: in expansion of macro 'bug'
  106 |     bug(pre[y],y);
      |     ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:107:5: note: in expansion of macro 'bug'
  107 |     bug("A",sz(vec));
      |     ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:110:9: note: in expansion of macro 'bug'
  110 |         bug(i);
      |         ^~~
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:116:5: note: in expansion of macro 'bug'
  116 |     bug("A",sz(vec));
      |     ^~~
Anna.cpp: In function 'void ReceiveA(bool)':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:155:17: note: in expansion of macro 'bug'
  155 |                 bug(sz(vec1),sz(vec2));
      |                 ^~~
Anna.cpp: In function 'int Answer()':
Anna.cpp:26:18: warning: statement has no effect [-Wunused-value]
   26 | #define bug(...) 826
      |                  ^~~
Anna.cpp:186:5: note: in expansion of macro 'bug'
  186 |     bug(res,sz(vec1),sz(vec2));
      |     ^~~
Anna.cpp: In function 'void {anonymous}::response(std::vector<int>, std::vector<int>, std::vector<int>&)':
Anna.cpp:70:9: warning: 'lpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     int lpos,rpos,cur=0,y;
      |         ^~~~
Anna.cpp:109:25: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |     rep2(i,y+1,sz(pre)) if(pre[i]<y){
      |                         ^~
Anna.cpp:12:37: warning: 'rpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 | #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                     ^
Anna.cpp:70:14: note: 'rpos' was declared here
   70 |     int lpos,rpos,cur=0,y;
      |              ^~~~
Anna.cpp:72:9: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |         if(tmp1[i]+cur>L){
      |         ^~
Anna.cpp:80:9: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |         if(tmp1[i]+cur>R){
      |         ^~

Bruno.cpp: In function 'std::vector<int> {anonymous}::Get(std::vector<int>&, int)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:54:36: note: in expansion of macro 'bug'
   54 |     if(sz(id)<100) for(auto i: id) bug(i);
      |                                    ^~~
Bruno.cpp:54:29: warning: unused variable 'i' [-Wunused-variable]
   54 |     if(sz(id)<100) for(auto i: id) bug(i);
      |                             ^
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:56:9: note: in expansion of macro 'bug'
   56 |         bug(sz(id));
      |         ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:67:13: note: in expansion of macro 'bug'
   67 |             bug(i);
      |             ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:70:9: note: in expansion of macro 'bug'
   70 |         bug("B",sz(res));
      |         ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:72:9: note: in expansion of macro 'bug'
   72 |         bug(val);
      |         ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:74:13: note: in expansion of macro 'bug'
   74 |             bug(i);
      |             ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:80:9: note: in expansion of macro 'bug'
   80 |         bug("B",sz(res));
      |         ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:87:42: note: in expansion of macro 'bug'
   87 |         if(sz(res)<100) for(auto i: res) bug(i);
      |                                          ^~~
Bruno.cpp:87:34: warning: unused variable 'i' [-Wunused-variable]
   87 |         if(sz(res)<100) for(auto i: res) bug(i);
      |                                  ^
Bruno.cpp: In function 'void InitB(int, std::vector<int>)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:111:5: note: in expansion of macro 'bug'
  111 |     bug(sz(tree1));
      |     ^~~
Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:139:13: note: in expansion of macro 'bug'
  139 |             bug(sz(tree2));
      |             ^~~
Bruno.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define bug(...) 826
      |                  ^~~
Bruno.cpp:157:13: note: in expansion of macro 'bug'
  157 |             bug(sz(tree2),sz(vec1),sz(vec2));
      |             ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 5 ms 480 KB Output is correct
4 Correct 9 ms 480 KB Output is correct
5 Correct 8 ms 476 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 8 ms 592 KB Output is correct
8 Correct 8 ms 496 KB Output is correct
9 Correct 8 ms 500 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 8 ms 592 KB Output is correct
12 Correct 8 ms 592 KB Output is correct
13 Correct 8 ms 600 KB Output is correct
14 Correct 8 ms 592 KB Output is correct
15 Correct 9 ms 480 KB Output is correct
16 Correct 8 ms 592 KB Output is correct
17 Correct 9 ms 388 KB Output is correct
18 Correct 7 ms 592 KB Output is correct
19 Correct 8 ms 588 KB Output is correct
20 Correct 9 ms 588 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 5 ms 480 KB Output is correct
4 Correct 9 ms 480 KB Output is correct
5 Correct 8 ms 476 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 8 ms 592 KB Output is correct
8 Correct 8 ms 496 KB Output is correct
9 Correct 8 ms 500 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 8 ms 592 KB Output is correct
12 Correct 8 ms 592 KB Output is correct
13 Correct 8 ms 600 KB Output is correct
14 Correct 8 ms 592 KB Output is correct
15 Correct 9 ms 480 KB Output is correct
16 Correct 8 ms 592 KB Output is correct
17 Correct 9 ms 388 KB Output is correct
18 Correct 7 ms 592 KB Output is correct
19 Correct 8 ms 588 KB Output is correct
20 Correct 9 ms 588 KB Output is correct
21 Correct 10 ms 736 KB Output is correct
22 Correct 10 ms 692 KB Output is correct
23 Correct 8 ms 732 KB Output is correct
24 Correct 8 ms 716 KB Output is correct
25 Correct 10 ms 736 KB Output is correct
26 Correct 9 ms 708 KB Output is correct
27 Correct 9 ms 732 KB Output is correct
28 Correct 9 ms 688 KB Output is correct
29 Correct 9 ms 732 KB Output is correct
30 Correct 6 ms 732 KB Output is correct
31 Correct 12 ms 708 KB Output is correct
32 Correct 8 ms 692 KB Output is correct
33 Incorrect 7 ms 292 KB Wrong Answer [2]
34 Halted 0 ms 0 KB -

Subtask #3
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 23964 KB Output is correct
2 Incorrect 20 ms 8188 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -