oj.uz

Submission #701845

# Submission time Handle Problem Language Result Execution time Memory
701845 2023-02-22T07:40:09 Z minhcool Shopping (JOI21_shopping) C++17
100 / 100
 419 ms 188520 KB 
#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;
}
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 528 KB Output is correct
2 Correct 1 ms 528 KB Output is correct
3 Correct 1 ms 528 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 1 ms 528 KB Output is correct
6 Correct 7 ms 656 KB Output is correct
7 Correct 9 ms 656 KB Output is correct
8 Correct 8 ms 656 KB Output is correct
9 Correct 4 ms 656 KB Output is correct
10 Correct 9 ms 656 KB Output is correct
11 Correct 7 ms 656 KB Output is correct
12 Correct 8 ms 656 KB Output is correct
13 Correct 7 ms 712 KB Output is correct
14 Correct 9 ms 656 KB Output is correct
15 Correct 9 ms 656 KB Output is correct
16 Correct 7 ms 656 KB Output is correct
17 Correct 8 ms 656 KB Output is correct
18 Correct 6 ms 656 KB Output is correct
19 Correct 9 ms 656 KB Output is correct
20 Correct 7 ms 656 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 528 KB Output is correct
2 Correct 1 ms 528 KB Output is correct
3 Correct 1 ms 528 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 1 ms 528 KB Output is correct
6 Correct 7 ms 656 KB Output is correct
7 Correct 9 ms 656 KB Output is correct
8 Correct 8 ms 656 KB Output is correct
9 Correct 4 ms 656 KB Output is correct
10 Correct 9 ms 656 KB Output is correct
11 Correct 7 ms 656 KB Output is correct
12 Correct 8 ms 656 KB Output is correct
13 Correct 7 ms 712 KB Output is correct
14 Correct 9 ms 656 KB Output is correct
15 Correct 9 ms 656 KB Output is correct
16 Correct 7 ms 656 KB Output is correct
17 Correct 8 ms 656 KB Output is correct
18 Correct 6 ms 656 KB Output is correct
19 Correct 9 ms 656 KB Output is correct
20 Correct 7 ms 656 KB Output is correct
21 Correct 9 ms 1808 KB Output is correct
22 Correct 10 ms 1808 KB Output is correct
23 Correct 9 ms 1808 KB Output is correct
24 Correct 9 ms 1828 KB Output is correct
25 Correct 8 ms 1820 KB Output is correct
26 Correct 7 ms 1808 KB Output is correct
27 Correct 9 ms 2064 KB Output is correct
28 Correct 9 ms 2448 KB Output is correct
29 Correct 11 ms 2064 KB Output is correct
30 Correct 9 ms 1936 KB Output is correct
31 Correct 8 ms 1808 KB Output is correct
32 Correct 9 ms 1808 KB Output is correct
33 Correct 8 ms 1808 KB Output is correct
34 Correct 11 ms 1808 KB Output is correct
35 Correct 10 ms 1808 KB Output is correct
36 Correct 11 ms 1808 KB Output is correct
37 Correct 10 ms 1808 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 124312 KB Output is correct
2 Correct 365 ms 125884 KB Output is correct
3 Correct 370 ms 125840 KB Output is correct
4 Correct 360 ms 125740 KB Output is correct
5 Correct 386 ms 157060 KB Output is correct
6 Correct 393 ms 188520 KB Output is correct
7 Correct 365 ms 127808 KB Output is correct
8 Correct 355 ms 127180 KB Output is correct
9 Correct 412 ms 125876 KB Output is correct
10 Correct 419 ms 125824 KB Output is correct
11 Correct 388 ms 125788 KB Output is correct
12 Correct 400 ms 125928 KB Output is correct
13 Correct 396 ms 125828 KB Output is correct
14 Correct 373 ms 125776 KB Output is correct
15 Correct 333 ms 125892 KB Output is correct
16 Correct 358 ms 141416 KB Output is correct
17 Correct 357 ms 131912 KB Output is correct
18 Correct 369 ms 129768 KB Output is correct
19 Correct 366 ms 127788 KB Output is correct
20 Correct 366 ms 126804 KB Output is correct
21 Correct 360 ms 126352 KB Output is correct
22 Correct 375 ms 126264 KB Output is correct
23 Correct 354 ms 126000 KB Output is correct
24 Correct 349 ms 125832 KB Output is correct
25 Correct 345 ms 125900 KB Output is correct
26 Correct 344 ms 125928 KB Output is correct
27 Correct 345 ms 125928 KB Output is correct
28 Correct 357 ms 125852 KB Output is correct
29 Correct 352 ms 125808 KB Output is correct
30 Correct 357 ms 125932 KB Output is correct