oj.uz

Submission #701815

# Submission time Handle Problem Language Result Execution time Memory
701815 2023-02-22T07:04:03 Z minhcool Shopping (JOI21_shopping) C++17
0 / 100
 474 ms 274420 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";
		ans = min(ans, {val, pos});
		lst_bits.clear();
	}
}

int Answer(){
    assert(ans.se != oo);
	//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];
 
set<int> 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";
		childs[pare].insert(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;
	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]]);
	for(auto v : childs[u]) prep2(v);
}
 
void ReceiveB(bool y) {
	assert(n > 10);
	c++;
	if(!y) 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++) 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 << cur_ask << "\n";
		//cout << ranges[cur_ask].fi << " " << ranges[cur_ask].se << "\n";
		sendnum(ranges[mn.se].fi), sendnum(ranges[mn.se].se);
	}
	else{
		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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47376 KB Output is correct
2 Incorrect 1 ms 200 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47376 KB Output is correct
2 Incorrect 1 ms 200 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 209868 KB Output is correct
2 Correct 434 ms 211788 KB Output is correct
3 Correct 438 ms 211832 KB Output is correct
4 Correct 460 ms 211856 KB Output is correct
5 Correct 458 ms 258836 KB Output is correct
6 Memory limit exceeded 474 ms 274420 KB
7 Halted 0 ms 0 KB -