제출 #250503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250503		lyc	Minerals (JOI19_minerals)	C++14	80 / 100	63 ms	3128 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

#define TRACE(x) std::cerr << #x << " :: " << x << std::endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 43005;

int inside[2*mxN];
int curVal, curAns;

int Add(int i) {
	if (!inside[i]) {
		inside[i] = true;
		curVal = Query(i);
	}
	return curVal;
}

int Del(int i) {
	if (inside[i]) {
		inside[i] = false;
		curVal = Query(i);
	}
	return curVal;
}

void Ans(int a, int b) { Answer(a,b); ++curAns; }

void rec(std::vector<int>& a, std::vector<int>& b) {
	//~ for (int x : a) std::cout << x << ' ';
	//~ std::cout << "| ";
	//~ for (int x : b) std::cout << x << ' ';
	//~ std::cout << std::endl;
	
	if (SZ(a) == 1) { Ans(a[0],b[0]); return; }
	
	int m = (SZ(a)-1)/2;
	std::vector<int> ax, ay, bx, by;
	FOR(i,0,m){
		ax.push_back(a[i]);
		Add(a[i]);
	}
	FOR(i,m+1,SZ(a)-1){
		ay.push_back(a[i]);
		Del(a[i]);
	}
	
	for (int& e : b) {
		int r = curVal;
		if (SZ(by) == SZ(ay) || (inside[e] ? Del(e) : Add(e)) == r) bx.push_back(e);
		else by.push_back(e);
	}
	
	rec(ax,bx);
	rec(ay,by);
}

void Solve(int N) {
	std::vector<int> a, b;
	
	int r = 0;
	FOR(i,1,2*N){
		int s = Add(i);
		if (s > r) a.push_back(i), r = s;
		else b.push_back(i);
	}
	
	rec(a,b);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10