Submission #1013569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013569		pcc	Rail (IOI14_rail)	C++17	100 / 100	201 ms	2964 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 5050;
map<pii,int> mp;
pii ans[mxn];

int Ask(int a,int b){
	if(mp.find(pii(a,b)) == mp.end())return mp[pii(a,b)] = mp[pii(b,a)] = getDistance(a,b);
	else return mp[pii(a,b)];
}

void Answer(int id,int pos,int tp){
	cerr<<"ANS: "<<id<<','<<pos<<','<<tp<<endl;
	if(ans[id].sc)cerr<<"REPEATED ANSWER: "<<id<<endl;
	assert(!ans[id].sc);
	ans[id] = pii(pos,tp);
}

int d1[mxn],d2[mxn];

void findLocation(int N, int ori, int location[], int stype[]){
	if(N == 1){
		location[0] = ori;
		stype[0] = 1;
		return;
	}
	vector<pii> da;
	for(int i = 0;i<N;i++)d1[i] = Ask(0,i);
	int a = 0,b = min_element(d1+1,d1+N)-d1;
	cerr<<"[a,b]: "<<a<<','<<b<<endl;

	Answer(b,ori+d1[b],2);
	cerr<<"INIT DONE!"<<endl;
	assert(a != b);
	vector<int> vl,vr;
	for(int i = 0;i<N;i++)d2[i] = Ask(b,i);
	int c = a;
	for(int i = 0;i<N;i++)if(i != b&&d2[i]<d2[c])c = i;
	for(int i = 0;i<N;i++){
		if(i == a||i == b)continue;
		int tmp = Ask(a,i)-Ask(b,i)+Ask(b,c);
		cerr<<i<<":"<<tmp<<endl;
		if(tmp == Ask(a,b)-Ask(b,c)||tmp == 0){
			cerr<<"VR: "<<i<<endl;
			vr.push_back(i);
		}
		else{
			cerr<<"VL: "<<i<<endl;
			vl.push_back(i);
		}
	}
	vl.push_back(a);
	sort(vl.begin(),vl.end(),[](int a,int b){return d2[a]<d2[b];});
	sort(vr.begin(),vr.end(),[](int a,int b){return d1[a]<d1[b];});

	/*
	{
		for(auto &i:vl)Answer(i,ans[b].fs-Ask(b,i),1);
		for(auto &i:vr)Answer(i,ans[a].fs+Ask(a,i),2);

		for(int i = 0;i<N;i++){
			if(!ans[i].sc)cerr<<"MISS ANS: "<<i<<endl;
			assert(ans[i].sc);
			location[i] = ans[i].fs;
			stype[i] = ans[i].sc;
		}
		assert(ans[a].fs == ori&&ans[a].sc == 1);
		return;
	}
	*/

	int lp = vl[0];
	vector<pii> pil;
	Answer(lp,ans[b].fs-Ask(b,lp),1);
	pil.push_back(pii(lp,ans[lp].fs));
	for(int i = 1;i<vl.size();i++){
		int now = vl[i];
		int d = Ask(lp,now);
		int isr = ans[lp].fs+d;
		int id = pil[0].fs;
		for(auto it = pil.rbegin();it != pil.rend();it++){
			if(it->sc<=isr)id = it->fs;
		}
		bool dir = 0;//dir = 0:left/1:right
		cerr<<now<<"::"<<isr<<' '<<id<<' '<<ans[id].fs<<' '<<Ask(b,now)<<endl;
		if(ans[id].fs >= isr||ans[b].fs<=isr)dir = 0;
		else if(isr-ans[id].fs+Ask(b,id) == Ask(b,now))dir = 1;
		else dir = 0;
		if(!dir){
			Answer(now,ans[b].fs-Ask(b,now),1);
			pil.push_back(pii(now,ans[now].fs));
		}
		else{
			Answer(now,isr,2);
		}
		lp = pil.back().fs;
	}

	cerr<<"LEFT DONE!"<<endl;
	pil.clear();
	assert(ans[a].sc);
	int rp = b;
	pil.push_back(pii(rp,ans[rp].fs));
	assert(vr.empty()||vr[0] != b);

	for(auto &now:vr){
		int d = Ask(rp,now);
		int isl = ans[rp].fs-d;
		int id = pil[0].fs;
		for(auto it = pil.rbegin();it != pil.rend();it++){
			if(it->sc>=isl)id = it->fs;
		}
		bool dir = 0;//dir = 0:out/1:in
		cerr<<now<<"::"<<id<<':'<<ans[id].fs<<','<<isl<<' '<<endl;
		if(ans[id].fs<=isl||isl<=ans[a].fs)dir = 0;
		else if(ans[id].fs-isl+Ask(a,id) == Ask(a,now))dir = 1;
		else dir = 0;
		if(!dir){
			Answer(now,ans[a].fs+Ask(a,now),2);
			pil.push_back(pii(now,ans[now].fs));
		}
		else{
			Answer(now,isl,1);
		}
		rp = pil.back().fs;
	}

	for(int i = 0;i<N;i++){
		if(!ans[i].sc)cerr<<"MISS ANS: "<<i<<endl;
		assert(ans[i].sc);
		location[i] = ans[i].fs;
		stype[i] = ans[i].sc;
	}

	return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 1;i<vl.size();i++){
      |                ~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44