oj.uz

Submission #283411

# Submission time Handle Problem Language Result Execution time Memory
283411 2020-08-25T16:37:04 Z rqi Rail (IOI14_rail) C++14
100 / 100
 110 ms 888 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define bk back()
#define pb push_back
#define all(x) begin(x), end(x)

const int MOD = 1000000007;
const int mx = 5005;
int pos1[mx];
int pos2[mx];

void findLocation(int N, int first, int location[], int stype[])
{
	// cout << "B1\n";
	// cout.flush();
	stype[0] = 1;
	location[0] = 0;
	pi mn = mp(MOD, -1);

	for(int i = 1; i < N; i++){
		pos1[i] = getDistance(0, i);
		mn = min(mn, mp(pos1[i], i));
	}

	stype[mn.s] = 2;
	location[mn.s] = mn.f;

	pi c = mp(mn.f, 0); //distance from mn.s

	for(int i = 1; i < N; i++){
		if(i == mn.s) continue;
		pos2[i] = getDistance(mn.s, i);
		c = min(c, mp(pos2[i], i));
	}
	c.f = mn.f-c.f; //position

	//cout << mn.f << " " << mn.s << " " << c.f << " " << c.s << "\n";
	// cout << "B2\n";
	// cout.flush();
	stype[c.s] = 1;
	location[c.s] = c.f;

	vpi lefs; //distance from a1, index
	vpi rigs; //distance from 0, index

	for(int i = 1; i < N; i++){
		if(i == mn.s || i == c.s) continue;
		int diff = pos1[i]-pos2[i];
		if(diff == mn.f){ //left of a1
			lefs.pb(mp(pos2[i], i));
		}
		else{ //right of a1
			rigs.pb(mp(pos1[i], i));
		}
	}

	sort(all(lefs));
	sort(all(rigs));
	// cout << "B3\n";
	// cout.flush();
	// cout << "lefs: \n";
	// for(auto u: lefs){
	// 	cout << u.f << " " << u.s << "\n";
	// }
	// cout << "rigs: \n";
	// for(auto u: rigs){
	// 	cout << u.f << " " << u.s << "\n";
	// }
	// cout << "\n";

	{
		vpi cur; //distance, index of C
		cur.pb(mp(mn.f, 0)); 
		for(auto u: lefs){
			if(u.f < mn.f){
				stype[u.s] = 1;
				location[u.s] = mn.f-u.f;
				continue;
			}
			int d = getDistance(cur.bk.s, u.s);
			int diff = u.f-d;
			bool case2 = 0;
			for(auto x: cur){
				if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
			}
			if(case2){
				stype[u.s] = 2;
				location[u.s] = mn.f-cur.bk.f+d;
			}
			else{
				stype[u.s] = 1;
				location[u.s] = mn.f-u.f;
				cur.pb(u);
			}
			// if(u.f != cur.f+d){
			// 	stype[u.s] = 1;
			// 	location[u.s] = mn.f-u.f;
			// 	cur = u;
			// }
			// else{
			// 	stype[u.s] = 2;
			// 	location[u.s] = mn.f-cur.f+d;
			// }
		}
	}
	


	{
		vpi cur; //distance, index of D
		cur.pb(mp(mn.f, mn.s));
		for(auto u: rigs){
			int d = getDistance(cur.bk.s, u.s);
			int diff = u.f-d;
			bool case2 = 0;
			for(auto x: cur){
				if(diff == x.f-(cur.bk.f-x.f)) case2 = 1;
			}
			if(case2){
				stype[u.s] = 1;
				location[u.s] = cur.bk.f-d;
			}
			else{
				stype[u.s] = 2;
				location[u.s] = u.f;
				cur.pb(u);
			}

			// if(u.f != cur.f+d){
			// 	cout << u.f << " " << u.s << "\n";
			// 	stype[u.s] = 2;
			// 	location[u.s] = u.f;
			// 	cur = u;
			// }
			// else{
			// 	stype[u.s] = 1;
			// 	location[u.s] = cur.f-d;
			// }
		}
	}
	

	for(int i = 0; i < N; i++){
		location[i]+=first;
		//cout << stype[i] << " " << location[i] << "\n";
	}
	// cout << "B5\n";
	// cout.flush();
	// stype[0] = 1;
	// location[0] = first;
	
	// pi mn = mp(MOD, -1);
	// for(int i = 1; i < N; i++){
	// 	pos1[i] = getDistance(0, i);
	// 	mn = min(mn, mp(pos1[i], i));
	// }

	// stype[mn.s] = 2;
	// location[mn.s] = first+mn.f;

	// for(int i = 1; i < N; i++){
	// 	if(i == mn.s) continue;
	// 	pos2[i] = getDistance(mn.s, i);
	// }

	// for(int i = 1; i < N; i++){
	// 	if(i == mn.s) continue;
	// 	if(pos1[i] > pos2[i]){
	// 		stype[i] = 1;
	// 		location[i] = first-(pos1[i]-2*mn.f);
	// 	}
	// 	else{
	// 		stype[i] = 2;
	// 		location[i] = first+pos1[i];
	// 	}
	// }


	// stype[0] = 1;
	// location[0] = first;
	// for(int i = 1; i < N; i++){
	// 	stype[i] = 2;
	// 	location[i] = location[0]+getDistance(0, i);
	// }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 504 KB Output is correct
2 Correct 88 ms 632 KB Output is correct
3 Correct 90 ms 632 KB Output is correct
4 Correct 88 ms 632 KB Output is correct
5 Correct 92 ms 632 KB Output is correct
6 Correct 92 ms 760 KB Output is correct
7 Correct 93 ms 760 KB Output is correct
8 Correct 88 ms 632 KB Output is correct
9 Correct 89 ms 632 KB Output is correct
10 Correct 90 ms 632 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 632 KB Output is correct
2 Correct 88 ms 632 KB Output is correct
3 Correct 90 ms 636 KB Output is correct
4 Correct 89 ms 696 KB Output is correct
5 Correct 92 ms 760 KB Output is correct
6 Correct 110 ms 648 KB Output is correct
7 Correct 99 ms 632 KB Output is correct
8 Correct 88 ms 632 KB Output is correct
9 Correct 90 ms 632 KB Output is correct
10 Correct 107 ms 632 KB Output is correct
11 Correct 94 ms 632 KB Output is correct
12 Correct 90 ms 632 KB Output is correct
13 Correct 99 ms 760 KB Output is correct
14 Correct 95 ms 632 KB Output is correct
15 Correct 104 ms 632 KB Output is correct
16 Correct 104 ms 632 KB Output is correct
17 Correct 102 ms 888 KB Output is correct
18 Correct 89 ms 636 KB Output is correct
19 Correct 91 ms 632 KB Output is correct
20 Correct 93 ms 632 KB Output is correct