Submission #1013487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013487		pcc	Rail (IOI14_rail)	C++17	30 / 100	99 ms	2072 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);
		if(tmp == Ask(a,c)){
			cerr<<"VL: "<<i<<endl;
			vl.push_back(i);
		}
		else{
			cerr<<"VR: "<<i<<endl;
			vr.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];
	Answer(lp,ans[b].fs-Ask(b,lp),1);
	for(int i = 1;i<vl.size();i++){
		int now = vl[i];
		if(Ask(lp,b)+Ask(lp,now) != Ask(b,now)){
			Answer(now,ans[b].fs-Ask(b,now),1);
			lp = now;
		}
		else{
			Answer(now,ans[lp].fs+Ask(lp,now),2);
		}
	}

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

	for(auto &now:vr){
		if(Ask(a,rp)+Ask(rp,now) != Ask(a,now)){
			Answer(now,ans[a].fs+Ask(a,now),2);
			rp = now;
		}
		else{
			Answer(now,ans[rp].fs-Ask(rp,now),1);
		}
	}

	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:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 1;i<vl.size();i++){
      |                ~^~~~~~~~~~

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