Submission #399762

#	Time	Username	Problem	Language	Result	Execution time	Memory
399762		Jasiekstrz	Rail (IOI14_rail)	C++17	100 / 100	99 ms	708 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
#define fi first
#define se second
using namespace std;
const int NN=5e3;
const int INF=1e9+7;
vector<pair<int,int>> t;
map<int,int> by_pos;
void findLocation(int N,int first,int location[],int stype[])
{
	location[0]=first;
	stype[0]=1;
	by_pos[first]=0;
	t.reserve(N+10);
	for(int i=1;i<N;i++)
		t.emplace_back(getDistance(0,i),i);
	sort(t.begin(),t.end());
	reverse(t.begin(),t.end());
	int a=0,b=0;
	b=t.back().se;
	stype[b]=2;
	location[b]=first+t.back().fi;
	by_pos[location[b]]=b;
	t.pop_back();
	while(!t.empty())
	{
		int v=t.back().se;
		int x=getDistance(a,v),y=getDistance(b,v),z=t.back().fi;
		t.pop_back();
		int c;
		int c1=location[a]+x;
		int c2=location[b]-y;
		int mid=(c1+c2)/2;
		//cerr<<v<<": a="<<a<<" b="<<b<<" x="<<x<<" y="<<y<<" z="<<z<<" c1="<<c1<<" c2="<<c2<<" ";
		if(by_pos.find(mid)!=by_pos.end())
		{
			if(stype[by_pos[mid]]==1)
				stype[v]=2;
			else
				stype[v]=1;
		}
		else if(first<mid)
			stype[v]=2;
		else // first>mid
			stype[v]=1;
		if(stype[v]==1)
			c=c2;
		else
			c=c1;
		location[v]=c;
		by_pos[c]=v;
		if(c>location[b])
			b=v;
		else if(c<location[a])
			a=v;
		//cerr<<"c="<<c<<"\n";
	}
	return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:45: warning: unused variable 'z' [-Wunused-variable]
   29 |   int x=getDistance(a,v),y=getDistance(b,v),z=t.back().fi;
      |                                             ^

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