Submission #1063267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063267		beaconmc	A Light Inconvenience (CEOI23_light)	C++17	100 / 100	712 ms	676 KiB

light

#include "light.h"

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

ll n, maxi;
vector<ll> prevs;

void prepare(){
	n = 1;
	maxi = n;
	prevs = {1};
}

pair<long long, std::vector<long long>> join(long long p){
	n += p;

	set<ll> stuff;
	stuff.insert(1);
	stuff.insert(n);
	for (auto&i : prevs){
		if (i != 1) stuff.insert(i+p);
	}
	vector<ll> real;
	for (auto&i : stuff) if (1<=i && i<=n) real.push_back(i);


	vector<ll> spare;
	FORNEG(i, real.size()-1, 0){
		//cout << (n-real[i] + 1)  << " " << (real[i] - real[i-1] - 1) << endl;
		while ((n-real[i] + 1) < (real[i] - real[i-1] - 1)){
			spare.push_back(real[i]);
			real[i] = n - (n-real[i] + 1)*2;
		}
	}
	for (auto&i : spare) real.push_back(i);
	sort(real.begin(), real.end());


	vector<ll> realreal;
	for (auto&i : real){
		while (realreal.size() >= 2 && ((n-i + 1) >= (i - realreal[realreal.size()-2] - 1))){

			realreal.pop_back();
		}
		realreal.push_back(i);
	}
	
	prevs = realreal;
	return {p,realreal};

}

std::pair<long long, std::vector<long long>> leave(long long p){
	n -= p;

	set<ll> stuff;
	stuff.insert(1);
	stuff.insert(n);
	for (auto&i : prevs){
		if (i != 1) stuff.insert(i);
	}
	vector<ll> real;
	for (auto&i : stuff) if (1<=i && i<=n) real.push_back(i);


	vector<ll> spare;
	FORNEG(i, real.size()-1, 0){
		//cout << (n-real[i] + 1)  << " " << (real[i] - real[i-1] - 1) << endl;
		while ((n-real[i] + 1) < (real[i] - real[i-1] - 1)){
			spare.push_back(real[i]);
			real[i] = n - (n-real[i] + 1)*2;
		}
	}
	for (auto&i : spare) real.push_back(i);
	sort(real.begin(), real.end());


	vector<ll> realreal;
	for (auto&i : real){
		while (realreal.size() >= 2 && ((n-i + 1) >= (i - realreal[realreal.size()-2] - 1))){

			realreal.pop_back();
		}
		realreal.push_back(i);
	}
	
	prevs = realreal;
	return {p,realreal};


}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 5 / 5
• Subtask 7: 60 / 60