Submission #619987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
619987	2022-08-02T18:15:40 Z	errorgorn	Minerals (JOI19_minerals)	C++17	70 / 100	338 ms	17244 KB

minerals

#include "minerals.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int num[50005];
int best[50005];
 
int CURR=0;
bool same(int x){
	int temp=Query(x);
	int res=CURR==temp;
	CURR=temp;
	return res;
}
 
int n;

vector<int> v; //singles
vector<ii> v2; //pairs
int B;

map<int,int> pos;

struct node{
	int len;
	vector<int> l; //indices
	node *L=nullptr,*R=nullptr;
	
	node (int _len){
		len=_len;
		
		if (len==1){
			l={v.back()}; v.pob();
		}
		else if (len==2 && !v2.empty()){
			l={v2.back().fi,v2.back().se}; v2.pob();
		}
		else{
			L=new node(best[len]);
			R=new node(len-best[len]);
			
			for (auto it:L->l) l.pub(it);
			for (auto it:R->l) l.pub(it);
		}
	}
	
	void solve(vector<int> r,bool in){
		if (L==nullptr){
			if (sz(r)==2){
				if (pos[r[0]]<B){
					Answer(l[0],r[0]);
					Answer(l[1],r[1]);
					return;
				}
				else{
					v=l;
					L=new node(1);
					R=new node(1);
				}
			}
			else{
				Answer(l[0],r[0]);
				return;
			}
		}
		
		for (auto it:L->l) same(it);
		
		vector<int> r1,r2;
		for (auto it:r){
			if (sz(L->l)==sz(r1)) r2.pub(it);
			else if (sz(R->l)==sz(r2)) r1.pub(it);
			else if (same(it) != in) r1.pub(it);
			else r2.pub(it);
		}
		
		L->solve(r1,!in);
		R->solve(r2,in);
	}
} *root;

vector<int> get(vector<int> inp){
	vector<int> temp,r;
	rep(x,0,sz(inp)){
		if (same(inp[x])) r.pub(inp[x]);
		else temp.pub(inp[x]);
	}
	
	vector<int> l,oth;
	for (auto it:temp){
		if (same(it)) l.pub(it);
		else oth.pub(it);
	}
	
	B=max(0LL,sz(l)/4);
	
	
	rep(x,0,B) v2.pub({l[x],l[sz(l)-1-x]});
	rep(x,B,sz(l)-B) v.pub(l[x]);
	root=new node(sz(l));
	
	rep(x,0,sz(r)) pos[r[x]]=x;
	root->solve(r,false);
	
	return oth;
}
 
void Solve(signed N) {
	num[1]=0;
	rep(x,2,50005){
		num[x]=1e9;
		int l=max(1LL,(int)(x*0.25)),r=min(x,(int)(x*0.4)+2);
		
		rep(y,l,r) if (num[x]>num[y]+num[x-y]+x+y){
			num[x]=num[y]+num[x-y]+x+y;
			best[x]=y;
		}
	}
	
	n=N;
	
	vector<int> idx;
	rep(x,1,2*n+1) idx.pub(x);
	shuffle(all(idx),rng);
	
	vector<int> l,r;
	rep(x,0,n) l.pub(idx[x]);
	rep(x,n,2*n) r.pub(idx[x]);
	
	l=get(l),r=get(r);
	if (sz(l)==0) return;
	v=l;
	root=new node(sz(l));
	root->solve(r,false);
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	299 ms	1380 KB	Output is correct
2	Correct	271 ms	1768 KB	Output is correct
3	Correct	268 ms	2640 KB	Output is correct
4	Correct	269 ms	4288 KB	Output is correct
5	Correct	286 ms	7240 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct

Subtask #4
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct
19	Incorrect	301 ms	11716 KB	Wrong Answer [5]
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct
19	Incorrect	301 ms	11716 KB	Wrong Answer [5]
20	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct
19	Incorrect	301 ms	11716 KB	Wrong Answer [5]
20	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct
19	Incorrect	301 ms	11716 KB	Wrong Answer [5]
20	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	1036 KB	Output is correct
2	Correct	259 ms	1068 KB	Output is correct
3	Correct	273 ms	1044 KB	Output is correct
4	Correct	258 ms	1044 KB	Output is correct
5	Correct	299 ms	1380 KB	Output is correct
6	Correct	271 ms	1768 KB	Output is correct
7	Correct	268 ms	2640 KB	Output is correct
8	Correct	269 ms	4288 KB	Output is correct
9	Correct	286 ms	7240 KB	Output is correct
10	Correct	266 ms	1332 KB	Output is correct
11	Correct	311 ms	5136 KB	Output is correct
12	Correct	280 ms	7324 KB	Output is correct
13	Correct	289 ms	7272 KB	Output is correct
14	Correct	281 ms	7208 KB	Output is correct
15	Correct	338 ms	17156 KB	Output is correct
16	Correct	331 ms	17244 KB	Output is correct
17	Correct	322 ms	17224 KB	Output is correct
18	Correct	334 ms	17020 KB	Output is correct
19	Incorrect	301 ms	11716 KB	Wrong Answer [5]
20	Halted	0 ms	0 KB	-

Submission #619987

Compilation message