oj.uz

Submission #619989

# Submission time Handle Problem Language Result Execution time Memory
619989 2022-08-02T18:16:38 Z errorgorn Minerals (JOI19_minerals) C++17
70 / 100
 356 ms 17664 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 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-20);
	
	
	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 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 1388 KB Output is correct
2 Correct 265 ms 1880 KB Output is correct
3 Correct 286 ms 2696 KB Output is correct
4 Correct 280 ms 4252 KB Output is correct
5 Correct 309 ms 7208 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct
19 Correct 336 ms 17664 KB Output is correct
20 Incorrect 301 ms 7964 KB Wrong Answer [5]
21 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct
19 Correct 336 ms 17664 KB Output is correct
20 Incorrect 301 ms 7964 KB Wrong Answer [5]
21 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct
19 Correct 336 ms 17664 KB Output is correct
20 Incorrect 301 ms 7964 KB Wrong Answer [5]
21 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct
19 Correct 336 ms 17664 KB Output is correct
20 Incorrect 301 ms 7964 KB Wrong Answer [5]
21 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1072 KB Output is correct
2 Correct 262 ms 1072 KB Output is correct
3 Correct 272 ms 1060 KB Output is correct
4 Correct 263 ms 1204 KB Output is correct
5 Correct 278 ms 1388 KB Output is correct
6 Correct 265 ms 1880 KB Output is correct
7 Correct 286 ms 2696 KB Output is correct
8 Correct 280 ms 4252 KB Output is correct
9 Correct 309 ms 7208 KB Output is correct
10 Correct 265 ms 1436 KB Output is correct
11 Correct 314 ms 5376 KB Output is correct
12 Correct 280 ms 7204 KB Output is correct
13 Correct 291 ms 7280 KB Output is correct
14 Correct 281 ms 7348 KB Output is correct
15 Correct 334 ms 17152 KB Output is correct
16 Correct 322 ms 17236 KB Output is correct
17 Correct 334 ms 17236 KB Output is correct
18 Correct 356 ms 17152 KB Output is correct
19 Correct 336 ms 17664 KB Output is correct
20 Incorrect 301 ms 7964 KB Wrong Answer [5]
21 Halted 0 ms 0 KB -