oj.uz

답안 #619988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619988 2022-08-02T18:16:14 Z errorgorn Minerals (JOI19_minerals) C++17
40 / 100
 354 ms 17268 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-5);
	
	
	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 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 1412 KB Output is correct
2 Correct 264 ms 1840 KB Output is correct
3 Correct 276 ms 2592 KB Output is correct
4 Correct 279 ms 4200 KB Output is correct
5 Correct 283 ms 7216 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 1060 KB Output is correct
2 Correct 259 ms 992 KB Output is correct
3 Correct 272 ms 1124 KB Output is correct
4 Correct 264 ms 1136 KB Output is correct
5 Correct 286 ms 1412 KB Output is correct
6 Correct 264 ms 1840 KB Output is correct
7 Correct 276 ms 2592 KB Output is correct
8 Correct 279 ms 4200 KB Output is correct
9 Correct 283 ms 7216 KB Output is correct
10 Correct 278 ms 1360 KB Output is correct
11 Correct 282 ms 5104 KB Output is correct
12 Correct 290 ms 7196 KB Output is correct
13 Correct 286 ms 7292 KB Output is correct
14 Correct 315 ms 7248 KB Output is correct
15 Correct 325 ms 17268 KB Output is correct
16 Correct 354 ms 17148 KB Output is correct
17 Incorrect 303 ms 7816 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -