Submission #1013452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013452		pcc	Rail (IOI14_rail)	C++17	30 / 100	85 ms	1940 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(a,ori,1);
		Answer(b,ori+d1[b],2);
		for(int i = 0;i<N;i++){
			if(i == a||i == b)continue;
			if(Ask(a,i)<Ask(b,i)){
				Answer(i,ans[a].fs+Ask(a,i),2);
			}
			else{
				Answer(i,ans[b].fs-Ask(b,i),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;
	}

	Answer(b,ori+d1[b],2);
	cerr<<"INIT DONE!"<<endl;
	assert(a != b);
	vector<int> vl,vr;
	for(int i = 0;i<N;i++){
		if(i == a||i == b)continue;
		d2[i] = Ask(b,i);
		if(d1[i]>=d2[i])vl.push_back(i);
		else vr.push_back(i);
		if(d1[i]>=d2[i])cerr<<"VL add: "<<i<<','<<d1[i]<<' '<<d2[i]<<endl;
		else cerr<<"VR add: "<<i<<','<<d1[i]<<' '<<d2[i]<<endl;
	}
	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]<d2[b];});
	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;
	int rp = 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:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 1;i<vl.size();i++){
      |                ~^~~~~~~~~~

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