oj.uz

답안 #619987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619987 2022-08-02T18:15:40 Z errorgorn Minerals (JOI19_minerals) C++17
70 / 100
 338 ms 17244 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);
	
	
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -