Submission #1305759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305759		AdamGS	Shopping (JOI21_shopping)	C++17	80 / 100	321 ms	58424 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
  int n, l, r, ile, aktl;
  vector<int>T;
	vector<int>pos;
  vector<bool>bits;
	ll ileb(ll dlu) {
		ll a=dlu*(dlu+1)/2;
		ll k=1;
		while((1ll<<k)<a) ++k;
		return k;
	}
	pair<ll,ll>desz(ll dlu, ll x) {
		for(ll i=0; i<dlu; ++i) {
			if(x>=(dlu-i)) {
				x-=dlu-i;
				continue;
			}
			return {i, i+x};
		}
		return {-1, -1};
	}
	ll szyf(ll dlu, pair<ll,ll>x) {
		ll k=x.nd-x.st;
		for(ll i=0; i<x.st; ++i) k+=dlu-i;
		return k;
	}
	void check() {
		++ile;
		ll k=0;
		rep(i, bits.size()) if(bits[i]) k|=1ll<<(ll)i;
		pair<ll,ll>p=desz(pos.size(), k);
		int a=p.st, b=p.nd;
		vector<int>tmp;
    bool zawiera=true;
    rep(i, pos.size()) if((i<a || i>b) && (l<=pos[i] && pos[i]<=r)) zawiera=false;
    if(zawiera) {
      SendA(1); 
      rep(i, pos.size()) if(pos[a]<=pos[i] && pos[i]<=pos[b]) tmp.pb(pos[i]);
    } else {
      SendA(0);
      rep(i, pos.size()) if(pos[a]>pos[i] || pos[i]>pos[b]) tmp.pb(pos[i]);
    }
    pos=tmp;
		bits.clear();
  }
int gentr(int d, int x) {
	int l=bits[aktl++];
	int r=bits[aktl++];
	int cnt=0;
	if(l) {
		int k=gentr(d+1, x);
		x+=k;
		cnt+=k;
	}
	T[x]=d;
	x+=1;
	cnt+=1;
	if(r) {
		int k=gentr(d+1, x);
		x+=k;
		cnt+=k;
	}
	return cnt;
}

}
void InitA(int _N, int _L, int _R) {
  n=_N; l=_L; r=_R; 
  ile=0;
  pos.clear();
  bits.clear();
  rep(i, n) pos.pb(i);
}
void ReceiveA(bool x) {
  bits.pb(x);
  assert(ileb(pos.size())<40);
	if(bits.size()==ileb(pos.size()) && ile<18) check();
}
int Answer() {
	T.resize(pos.size());
	aktl=0;
	gentr(0, 0);
  pair<int,int>mi={n, n};
  rep(i, pos.size()) if(l<=pos[i] && pos[i]<=r) mi=min(mi, {T[i], pos[i]});
  return mi.nd;
}
//???

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
  const int LIM=1e6+7;
  int lewo[LIM], prawo[LIM], odw[LIM], n, ile;
  pair<int,int>xd;
  vector<int>T, pos;
	ll ileb(ll dlu) {
		ll a=dlu*(dlu+1)/2;
		ll k=1;
		while((1ll<<k)<a) ++k;
		return k;
	}
	pair<ll,ll>desz(ll dlu, ll x) {
		for(ll i=0; i<dlu; ++i) {
			if(x>=(dlu-i)) {
				x-=dlu-i;
				continue;
			}
			return {i, i+x};
		}
		return {-1, -1};
	}
	ll szyf(ll dlu, pair<ll,ll>x) {
		ll k=x.nd-x.st;
		for(ll i=0; i<x.st; ++i) k+=dlu-i;
		return k;
	}

	void send() {
    int m=pos.size();
    vector<pair<int,int>>P, S;
    rep(i, m) {
      lewo[i]=prawo[i]=i;
      odw[i]=0;
      P.pb({T[pos[i]], i});
    }
    sort(all(P));
    reverse(all(P));
    for(auto i : P) {
      int l=i.nd, r=i.nd;
      if(l && odw[l-1]) {
        lewo[r]=lewo[l-1];
        prawo[lewo[r]]=r;
        l=lewo[r];
      }
      if(r<m-1 && odw[r+1]) {
        prawo[l]=prawo[r+1];
        lewo[prawo[l]]=l;
        r=prawo[l];
      }
      odw[i.nd]=1;
      S.pb({l, r});
    }
    pair<int,int>mi={LIM, LIM};
    rep(i, m) {
      int d=S[i].nd-S[i].st+1;
      mi=min(mi, {max(d, (int)pos.size()-d), i});
    }
    xd=S[mi.nd];
		ll k=szyf(pos.size(), S[mi.nd]);
		assert(ileb(pos.size()));
		rep(i, ileb(pos.size())) if(k&(1ll<<(ll)i)) SendB(1); else SendB(0);
  }
	void sendtr(int l, int r) {
		if(l==r) {
			SendB(0);
			SendB(0);
			return;
		}
		pair<int,int>mi={n, n};
		for(int i=l; i<=r; ++i) mi=min(mi, {T[pos[i]], i});
		int a=0, b=0;
		if(l<mi.nd) a=1;
		if(mi.nd<r) b=1;
		SendB(a);
		SendB(b);
		if(a) sendtr(l, mi.nd-1);
		if(b) sendtr(mi.nd+1, r);
	}
}
void InitB(int _N, vector<int>_T) {
  n=_N; ile=0;
  T=_T;
  pos.clear();
  rep(i, n) pos.pb(i);
  send();
}
void ReceiveB(bool y) {
  ++ile;
  vector<int>tmp;
  if(y) {
    rep(i, pos.size()) if(xd.st<=i && i<=xd.nd) tmp.pb(pos[i]);
  } else {
    rep(i, pos.size()) if(xd.st>i || i>xd.nd) tmp.pb(pos[i]);
  }
  pos=tmp;
  if(ile<18) {
    send();
    return;
  }
	sendtr(0, (int)pos.size()-1);
}

• Subtask 1: 1 / 1
• Subtask 2: 9 / 9
• Subtask 3: 70 / 90