제출 #832659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832659		Antekb	Fun Tour (APIO20_fun)	C++17	19 / 100	136 ms	21180 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=2e5+5;
struct node{
	int id, gleb=0;
	node* l=nullptr, *r=nullptr, *par=nullptr;
	node(int id): id(id){}

};
bool czy[N];
int gleb[N];
int find_dist(node* v){
	//deb("a");
	if(!v->par)return 0;
	if(v==v->par->l){
		if(v->par->r)return max(find_dist(v->par)+1, v->par->r->gleb+2);
		else return find_dist(v->par)+1;
	}
	else{
		//deb(v->id);
		if(v->par->l)return max(find_dist(v->par)+1, v->par->l->gleb+2);
		else return find_dist(v->par)+1;
	}
}
void upd(node*v){
	v->gleb=0;
	if(v->l)v->gleb=v->l->gleb+1;
	if(v->r)v->gleb=max(v->gleb, v->r->gleb+1);
}
node* find(node* v, int dist, int t){
	//deb("c");deb(v, dist, t);
	if(v){
		//deb(v, dist, t)
	}
	//deb(v->id, dist);
	if(dist==0)return v;
	if(t){
		if(v->l && v->l->gleb==dist-1)return find(v->l, dist-1, 1);
		else return find(v->r, dist-1, 1);
	}
	if(v==v->par->l && v->par->r && dist==v->par->r->gleb+2)return find(v->par->r, dist-2, 1);
	if(v==v->par->r && v->par->l && dist==v->par->l->gleb+2)return find(v->par->l, dist-2, 1);
	return find(v->par, dist-1, 0);
}
vector<node*> nodes;
vi dep;
node* solve(int l, int r){
	if(l>r)return 0;
	int m=l;
	for(int i=l; i<=r; i++){
		if(dep[i]<dep[m])m=i;
	}
	node* u=solve(l, m-1), *v=solve(m+1, r);
	nodes[m]->l=u;
	nodes[m]->r=v;
	if(v)v->par=nodes[m];
	if(u)u->par=nodes[m];
	upd(nodes[m]);
	return nodes[m];
}
std::vector<int> createFunTour(int n, int Q) {
	//int H = hoursRequired(0, N - 1);
	//int A = attractionsBehind(0, N - 1);
	vi V={0};
	int dd=hoursRequired(0, n - 1);
	for(int i=1; i<n-1; i++){
		if(hoursRequired(0, i)+hoursRequired(i, n - 1)==dd){
			V.pb(i);
		}
	}
	V.pb(n-1);
	int l=n, r=-1;
	for(int i:V){
		if(i!=n-1 && attractionsBehind(i+1, i)!=i+1)r=max(r, i+1);
		if(i && attractionsBehind(i-1, i)!=n-i)l=min(l, i-1);
	}
	int t=-1;
	for(int i:V){
		if(i<=l && i>=r){
			t=i;
			break;
		}
	}
	deb(t, l, r, V.size());
	dep.resize(n);
	for(int i=0; i<n; i++){
		dep[i]=hoursRequired(t, i);
	}
	for(int i=0; i<n; i++){
		nodes.pb(new node(i));
	}
	vi ans;
	node* root=solve(0, n-1);
	/*for(int i=0; i<n; i++){
		deb(i, nodes[i]->id, nodes[i]->gleb);
		node*v=nodes[i];
		if(v->l){deb(v->l->id);}
		if(v->r){deb(v->r->id);}
		if(v->par){deb(v->par->id);}
	}*/
	ans.pb(find(root, root->gleb, 1)->id);
	while(ans.size()<n){
		//deb(ans.back());
		if(ans.back()==root->id){
			//deb("a");
			int d=root->gleb;
			node*v=find(root, d, 1);
			if(root->l==0){
				root->r->par=0;
				root=root->r;
			}
			else{
				root->l->par=0;
				root=root->l;
			}
			ans.pb(v->id);
		}
		else{
			node*v=nodes[ans.back()];
			int d=find_dist(v);
			node*u=find(v, d, 0);
			//deb(v->id, u->id, d);
			if(v==v->par->l)v->par->l=0;
			else v->par->r=0;
			while(v->par){
				v=v->par;
				upd(v);
			}
			ans.pb(u->id);
		}
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:127:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |  while(ans.size()<n){
      |        ~~~~~~~~~~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 34