제출 #832638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832638		Antekb	즐거운 행로 (APIO20_fun)	C++17	21 / 100	90 ms	20748 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;
std::vector<int> createFunTour(int n, int Q) {
	//int H = hoursRequired(0, N - 1);
	//int A = attractionsBehind(0, N - 1);
	for(int i=0; i<n; i++){
		nodes.pb(new node(i));
		if(i){
			nodes[i]->par=nodes[(i-1)/2];
			if(i&1)nodes[i]->par->l=nodes[i];
			else nodes[i]->par->r=nodes[i];
		}
	}
	for(int i=n-1; i>=0; i--){
		upd(nodes[i]);
	}
	vi ans;
	node* root=nodes[0];
	/*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:95:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |  while(ans.size()<n){
      |        ~~~~~~~~~~^~

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