oj.uz

Submission #619997

# Submission time Handle Problem Language Result Execution time Memory
619997 2022-08-02T18:24:14 Z errorgorn Minerals (JOI19_minerals) C++17
100 / 100
 359 ms 19416 KB 
#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 B1,B2;

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){
		shuffle(all(r),rng);
		
		if (L==nullptr){
			if (sz(r)==2){
				if (pos[r[0]]>pos[r[1]]) swap(r[0],r[1]);
				
				if (pos[r[0]]<B1){
					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);
	}
	
	B1=max(0LL,sz(l)/4-50);
	B2=max(0LL,sz(l)/4);
	
	rep(x,0,B2) v2.pub({l[x],l[sz(l)-1-x]});
	rep(x,B2,sz(l)-B2) 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 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 1436 KB Output is correct
2 Correct 263 ms 1808 KB Output is correct
3 Correct 274 ms 2636 KB Output is correct
4 Correct 273 ms 4244 KB Output is correct
5 Correct 307 ms 7180 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct
19 Correct 339 ms 17760 KB Output is correct
20 Correct 329 ms 17708 KB Output is correct
21 Correct 348 ms 17624 KB Output is correct
22 Correct 328 ms 17472 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct
19 Correct 339 ms 17760 KB Output is correct
20 Correct 329 ms 17708 KB Output is correct
21 Correct 348 ms 17624 KB Output is correct
22 Correct 328 ms 17472 KB Output is correct
23 Correct 338 ms 18144 KB Output is correct
24 Correct 343 ms 18104 KB Output is correct
25 Correct 340 ms 18104 KB Output is correct
26 Correct 343 ms 18084 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct
19 Correct 339 ms 17760 KB Output is correct
20 Correct 329 ms 17708 KB Output is correct
21 Correct 348 ms 17624 KB Output is correct
22 Correct 328 ms 17472 KB Output is correct
23 Correct 338 ms 18144 KB Output is correct
24 Correct 343 ms 18104 KB Output is correct
25 Correct 340 ms 18104 KB Output is correct
26 Correct 343 ms 18084 KB Output is correct
27 Correct 338 ms 18504 KB Output is correct
28 Correct 344 ms 18576 KB Output is correct
29 Correct 346 ms 18620 KB Output is correct
30 Correct 328 ms 18380 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct
19 Correct 339 ms 17760 KB Output is correct
20 Correct 329 ms 17708 KB Output is correct
21 Correct 348 ms 17624 KB Output is correct
22 Correct 328 ms 17472 KB Output is correct
23 Correct 338 ms 18144 KB Output is correct
24 Correct 343 ms 18104 KB Output is correct
25 Correct 340 ms 18104 KB Output is correct
26 Correct 343 ms 18084 KB Output is correct
27 Correct 338 ms 18504 KB Output is correct
28 Correct 344 ms 18576 KB Output is correct
29 Correct 346 ms 18620 KB Output is correct
30 Correct 328 ms 18380 KB Output is correct
31 Correct 335 ms 18980 KB Output is correct
32 Correct 345 ms 18976 KB Output is correct
33 Correct 336 ms 19076 KB Output is correct
34 Correct 359 ms 18760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 976 KB Output is correct
2 Correct 256 ms 1144 KB Output is correct
3 Correct 267 ms 1064 KB Output is correct
4 Correct 269 ms 1128 KB Output is correct
5 Correct 281 ms 1436 KB Output is correct
6 Correct 263 ms 1808 KB Output is correct
7 Correct 274 ms 2636 KB Output is correct
8 Correct 273 ms 4244 KB Output is correct
9 Correct 307 ms 7180 KB Output is correct
10 Correct 267 ms 1432 KB Output is correct
11 Correct 292 ms 5104 KB Output is correct
12 Correct 286 ms 7284 KB Output is correct
13 Correct 302 ms 7284 KB Output is correct
14 Correct 278 ms 7204 KB Output is correct
15 Correct 344 ms 17156 KB Output is correct
16 Correct 326 ms 17156 KB Output is correct
17 Correct 333 ms 17224 KB Output is correct
18 Correct 338 ms 17036 KB Output is correct
19 Correct 339 ms 17760 KB Output is correct
20 Correct 329 ms 17708 KB Output is correct
21 Correct 348 ms 17624 KB Output is correct
22 Correct 328 ms 17472 KB Output is correct
23 Correct 338 ms 18144 KB Output is correct
24 Correct 343 ms 18104 KB Output is correct
25 Correct 340 ms 18104 KB Output is correct
26 Correct 343 ms 18084 KB Output is correct
27 Correct 338 ms 18504 KB Output is correct
28 Correct 344 ms 18576 KB Output is correct
29 Correct 346 ms 18620 KB Output is correct
30 Correct 328 ms 18380 KB Output is correct
31 Correct 335 ms 18980 KB Output is correct
32 Correct 345 ms 18976 KB Output is correct
33 Correct 336 ms 19076 KB Output is correct
34 Correct 359 ms 18760 KB Output is correct
35 Correct 355 ms 19416 KB Output is correct
36 Correct 349 ms 19372 KB Output is correct
37 Correct 338 ms 19300 KB Output is correct
38 Correct 344 ms 19260 KB Output is correct