oj.uz

Submission #66974

# Submission time Handle Problem Language Result Execution time Memory
66974 2018-08-13T04:38:30 Z Namnamseo Rail (IOI14_rail) C++17
100 / 100
 122 ms 20460 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int,int>;
#define all(v) (v).begin(), (v).end()
#define pb push_back

int dcache[5000][5000];
int get_dist(int a, int b){
	if(dcache[a][b]) return dcache[a][b]-1;
	int d = getDistance(a, b);
	dcache[a][b] = d+1;
	return d;
}

#define printf if(0) printf

vector<pp> ds;
vector<int> lv, rv;
bool ex[1000010];
bool ex2[1000010];
void findLocation(int n, int first, int location[], int stype[])
{
	if(n == 1){
		location[0] = first;
		stype[0] = 1;
		return;
	}

	for(int i=1; i<n; ++i) ds.emplace_back(get_dist(0, i), i);
	sort(all(ds));

	int diam, ri;
	tie(diam, ri) = ds[0];
	int rp = first + diam;

	location[0] = first; stype[0] = 1;
	location[ri] = rp; stype[ri] = 2;

	for(int t=1; t<n-1; ++t){
		int i = ds[t].second;
		int dl = get_dist(0, i);
		int dr = get_dist(ri, i);

		if(dr < diam && dl == diam + dr){
			location[i] = rp - dr;
			stype[i] = 1;
			continue;
		}

		if(dl == dr + diam) lv.pb(i);
		else rv.pb(i);
	}

	int lp = first, li = 0;
	for(int i : lv){
		int ld = get_dist(li, i);
		int tm = (rp - lp) + ld - get_dist(ri, i);
		tm /= 2;
		if(lp + tm <= int(1e6) && ex[lp+tm]){
			location[i] = lp + ld;
			stype[i] = 2;
		} else {
			lp = rp - get_dist(ri, i);
			li = i;
			location[i] = lp;
			stype[i] = 1;
			ex[lp] = 1;
		}
	}

	for(int i : rv){
		int rd = get_dist(ri, i);
		int tm = (rp-first) + rd - get_dist(0, i);
		tm /= 2;
		if(0 <= rp-tm && ex2[rp-tm]){
			location[i] = rp - rd;
			stype[i] = 1;
		} else {
			rp = first + get_dist(0, i);
			ri = i;
			location[i] = rp;
			stype[i] = 2;
			ex2[rp] = 1;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 944 KB Output is correct
4 Correct 3 ms 944 KB Output is correct
5 Correct 2 ms 944 KB Output is correct
6 Correct 3 ms 960 KB Output is correct
7 Correct 2 ms 960 KB Output is correct
8 Correct 3 ms 976 KB Output is correct
9 Correct 3 ms 976 KB Output is correct
10 Correct 3 ms 1020 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 18912 KB Output is correct
2 Correct 113 ms 18964 KB Output is correct
3 Correct 111 ms 19192 KB Output is correct
4 Correct 108 ms 19192 KB Output is correct
5 Correct 113 ms 19192 KB Output is correct
6 Correct 113 ms 19192 KB Output is correct
7 Correct 122 ms 19272 KB Output is correct
8 Correct 119 ms 19352 KB Output is correct
9 Correct 109 ms 19504 KB Output is correct
10 Correct 112 ms 19504 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 19504 KB Output is correct
2 Correct 111 ms 19692 KB Output is correct
3 Correct 112 ms 19808 KB Output is correct
4 Correct 115 ms 19808 KB Output is correct
5 Correct 114 ms 19808 KB Output is correct
6 Correct 113 ms 19808 KB Output is correct
7 Correct 121 ms 19808 KB Output is correct
8 Correct 112 ms 19808 KB Output is correct
9 Correct 106 ms 19808 KB Output is correct
10 Correct 107 ms 19856 KB Output is correct
11 Correct 109 ms 20016 KB Output is correct
12 Correct 106 ms 20064 KB Output is correct
13 Correct 106 ms 20064 KB Output is correct
14 Correct 107 ms 20096 KB Output is correct
15 Correct 121 ms 20096 KB Output is correct
16 Correct 114 ms 20136 KB Output is correct
17 Correct 105 ms 20136 KB Output is correct
18 Correct 113 ms 20460 KB Output is correct
19 Correct 107 ms 20460 KB Output is correct
20 Correct 116 ms 20460 KB Output is correct