Submission #701845

#	Time	Username	Problem	Language	Result	Execution time	Memory
701845		minhcool	Shopping (JOI21_shopping)	C++17	100 / 100	419 ms	188520 KiB

Anna

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int nn, l, r;

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

int cnt1 = 0, cnt2 = 0;

vector<int> lst_bits;

ii ans = {oo, oo};

void ReceiveA(bool x){
	cnt1++;
	lst_bits.pb(x);
	//cout << cnt1 << "\n";
	if(nn > 10){
		if(cnt1 % 40) return;
		if(cnt2 < 18){
			int le = 0, ri = 0;
			for(int i = 0; i < 20; i++) le = (le * 2 + lst_bits[i]);
			for(int i = 0; i < 20; i++) ri = (ri * 2 + lst_bits[i + 20]);
			if(le <= l && ri >= r) SendA(1);
			else SendA(0);
			lst_bits.clear();
			cnt2++;
		}
		else{
			int pos = 0, val = 0;
			for(int i = 0; i < 20; i++) pos = (pos * 2 + lst_bits[i]);
			for(int i = 0; i < 20; i++) val = (val * 2 + lst_bits[i + 20]);
			if(l <= pos && pos <= r) ans = min(ans, {val, pos});
			lst_bits.clear();
		}
	}
	else{
		if(cnt1 % 20) return;
		int pos = (cnt1 / 20), val = 0;
		for(int i = 0; i < 20; i++) val = (val * 2 + lst_bits[i]);
		//cout << pos << " " << val << "\n";
		if(l <= pos && pos <= r) ans = min(ans, {val, pos});
		lst_bits.clear();
	}
}

int Answer(){
	//cout << ans.fi << " " << ans.se << "\n";
	return ans.se - 1;
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, arr[N];
int mini[N][21];
 
int mn_pos(int l, int r){
	int k = log2(r - l + 1);
	if(arr[mini[l][k]] < arr[mini[r - (1LL << k) + 1][k]]) return mini[l][k];
	else return mini[r - (1LL << k) + 1][k];
}
 
int cnt, par[N];
 
ii childs[N];
ii ranges[N];
 
int pos[N];
 
void build(int l, int r, int pare){
	if(l > r) return;
	int temp = mn_pos(l, r);
	cnt++;
	pos[cnt] = temp;
	if(pare){
		//cout << cnt << " " << pare << " " << l << " " << r << "\n";
		if(!childs[pare].fi) childs[pare].fi = cnt;
		else childs[pare].se = cnt;
		par[cnt] = pare;
	}
	ranges[cnt] = {l, r};
	int tempo = cnt;
	build(l, temp - 1, tempo);
	build(temp + 1, r, tempo);
}
 
int cur_root, cur_ask;
 
int sz[N];
 
void prep(int u){
	sz[u] = 1;
	if(childs[u].fi){
		prep(childs[u].fi);
		sz[u] += sz[childs[u].fi];
	}
	if(childs[u].se){
		prep(childs[u].se);
		sz[u] += sz[childs[u].se];
	}
	/*
	for(auto v : childs[u]){
		prep(v);
		sz[u] += sz[v];
	}*/
}
 
void sendnum(int x){
	//cout << x << "\n";
	for(int i = 19; i >= 0; i--){
		SendB((x & (1LL << i)) != 0);
	}
}
 
void InitB(int nn, vector<int> P){
	n = nn;
	///P.push_front(0);
	vector<int> P2;
	P2.pb(0);
	for(auto it : P) P2.pb(it);
	P = P2;
	for(int i = 1; i <= n; i++) arr[i] = P[i];
	for(int i = 1; i <= n; i++) mini[i][0] = i;
	for(int i = 1; i <= 19; i++){
		for(int j = 1; (j + (1LL << i) - 1) <= n; j++){
			int temp1 = P[mini[j][i - 1]], temp2 = P[mini[j + (1LL << (i - 1))][i - 1]];
			if(temp1 < temp2) mini[j][i] = mini[j][i - 1];
			else mini[j][i] = mini[j + (1LL << (i - 1))][i - 1];
		}
	}
	build(1, n, 0);
	if(n > 10){
		cur_root = 1;
		for(int i = 1; i <= n; i++) sz[i] = 0;
		prep(cur_root);
		ii mn = {oo, oo};
		for(int i = 1; i <= n; i++) mn = min(mn, {abs(sz[i] - n/2), i});
		cur_ask = mn.se;
		//cout << cur_ask << " " << ranges[cur_ask].fi << " " << ranges[cur_ask].se << "\n";
		sendnum(ranges[mn.se].fi), sendnum(ranges[mn.se].se);
		/*
		cur_root = 1, cur_ask = find_cen(1);
		ii mx = {-1, -1};
		for(auto v : child[cur_ask]) mx = max(mx, {sz[v], v});
		cur_ask = v.se;
		sendnum(range[cur_ask].fi);
		sendnum(range[cur_ask].se);*/
		//for(int i = 0; i <= 19; i++) SendB()
	}
	else{
		//cout << "OK\n" << n << "\n";
		for(int i = 1; i <= n; i++) sendnum(P[i]);
	}
}
 
int c = 0;
 
void prep2(int u){
	sendnum(pos[u]);
	sendnum(arr[pos[u]]);
	if(childs[u].fi) prep2(childs[u].fi);
	if(childs[u].se) prep2(childs[u].se);
	//for(auto v : childs[u]) prep2(v);
}
 
void ReceiveB(bool y) {
	assert(n > 10);
	c++;
	if(!y){
		if(childs[par[cur_ask]].fi == cur_ask) childs[par[cur_ask]].fi = 0;
		else childs[par[cur_ask]].se = 0;
		//childs[par[cur_ask]].erase(cur_ask);
	}
	else cur_root = cur_ask;
	//cout << cur_root << "\n";
	if(c < 18){
		for(int i = 1; i <= n; i++) sz[i] = 0;
		prep(cur_root);
		ii mn = {oo, oo};
		for(int i = 1; i <= n; i++) if(sz[i] != 0) mn = min(mn, {abs(sz[i] - sz[cur_root]/2), i});
		//for(int i = 1; i <= n; i++) cout << i << " " << sz[i] << "\n";
		cur_ask = mn.se;
		//cout << sz[cur_ask] << "\n";
		//cout << cur_ask << "\n";
		//cout << ranges[cur_ask].fi << " " << ranges[cur_ask].se << "\n";
		sendnum(ranges[mn.se].fi), sendnum(ranges[mn.se].se);
	}
	else{
		prep(cur_root);
		//cout << sz[cur_root] << "\n";
		prep2(cur_root);
	}
}
 
/*
20 9 16
5 7 10 8 6 3 2 1 9 4 12 15 18 20 19 17 14 13 16 11
*/

Compilation message (stderr)

Anna.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Bruno.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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