Submission #1166348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166348		fabijan_cikac	Rail (IOI14_rail)	C++20	30 / 100	1059 ms	99020 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

#define pb push_back

struct S{
	int loc, id, t;
};

const int MAXN = 5010;

int N;
vector<S> b;
int dist[MAXN][MAXN];

/*int getDistance(int x, int y){
	cout << "? " << x << ' ' << y << endl;
	int z; cin >> z; return z;
}*/

int D(int x, int y){
	if (dist[x][y] != -1) return dist[x][y];
	if (x == y) return dist[x][y] = 0;
	return dist[x][y] = getDistance(x, y);
}

bool cmp1(int x, int y){ return D(0, x) < D(0, y); }
bool cmp2(S x, S y){ return x.loc < y.loc; }

//int location[MAXN]; int stype[MAXN];
void findLocation(int n, int first, int location[], int stype[]){
	//cout << "ok" << endl;
	memset(dist, -1, sizeof(dist)); N = n;
	
	vector<int> a;
	for (int i = 1; i < N; ++i) a.pb(i);
	
	sort(a.begin(), a.end(), cmp1);
	//cout << "b" << endl;
	S L = {first, 0, 0}, R = {first + D(0, a[0]), a[0], 1};
	
	b.pb(L), b.pb(R);
	for (int i = 1; i < (int)(a.size()); ++i){
		int x = a[i];
		//is he directly connected to L
		int lx = L.loc + D(x, L.id);
		
		//cout << " ??? " << x << ' ' << lx << " :: " << L.loc << ' ' << L.id << ' ' << L.t << " -- " << R.loc << ' ' << R.id << ' ' << R.t << endl;
		
		int P = 1e9;
		for (auto p: b)
			if (p.loc < min(lx, R.loc) && !p.t) P = p.loc;
		bool good = 0;
		if ((lx - P) + (R.loc - P) == D(x, R.id)) good = 1;
		
		//cout << ">>> " << P << ' ' << good << endl;
		
		if (good){
			//cout << " !!! " << x << ' ' << lx << endl;
			S nw = {lx, x, 1}; b.pb(nw);
			if (nw.loc > R.loc) R = nw;
		}
		else{
			S nw = {R.loc - D(x, R.id), x, 0}; b.pb(nw);
			//cout << " !!! " << x << ' ' << nw.loc << endl;
			if (nw.loc < L.loc) L = nw;
		}
		
		sort(b.begin(), b.end(), cmp2);
	}
	
	for (auto p: b){
		//cout << "F: " << p.id << ": " << p.loc << ' ' << p.t << endl;
		location[p.id] = p.loc, stype[p.id] = p.t + 1;
	}
	
	/*for (int i = 0; i < N; ++i)
		cout << location[i] << ' ';
	cout << endl;*/
	/*for (int i = 0; i < N; ++i)
		cout << stype[i] << ' ';
	cout << endl;*/
	
	return;
}

/*int main(){
	findLocation(5, 1);
	return 0;
}*/

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