oj.uz

Submission #603319

# Submission time Handle Problem Language Result Execution time Memory
603319 2022-07-24T00:54:32 Z farhan132 Rail (IOI14_rail) C++17
100 / 100
 113 ms 98804 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert


const ll N = 5005;

ll dist[N][N];

ll D_(ll i, ll j){
	if(i == j) return 0;
	if(dist[i][j] != -1) return dist[i][j];
	dist[i][j] = dist[j][i] = getDistance(i, j);
	return dist[i][j];
}

void findLocation(int n, int first, int location[], int stype[]){

	memset(dist, -1, sizeof(dist));

	ii mn = {1e9, 0};
	location[0] = first; stype[0] = 1;
	if(n == 1) return;

	vector < ll > all;
	set < ii > C,D;

	for(ll i = 1; i < n; i++){
		all.pb(i);
	}
	sort(all.begin(), all.end(),[&](ll i, ll j){
		return D_(0, i) < D_(0, j);
	});

	C.in({first, 0});
	D.in({first + D_(0, all[0]), all[0]});
	ll l = 0, r = all[0];
	location[r] = first + D_(l, r);
	stype[r] = 2;

	for(auto i : all){
		if(i == r) continue;
		// L i R (C)
		ll x = D_(l, i);
		ll y = D_(r, i);
		ll ex = location[r] - y;
		if(ex >= first){
			auto [pos, j] = *D.lower_bound({ex, 0} );
			if(pos != ex && x == pos - location[l] + pos - ex){
				location[i] = ex;
				stype[i] = 1; // C
				C.in({location[i], i});
				continue;
			}
		}
		// L i R (D)
		ex = location[l] + x;
		if(ex <= first){
			auto [pos, j] = *(--C.upper_bound({ex, 1e9}));
			if(pos != ex && y == location[r] - pos + ex - pos){
				location[i] = ex;
				stype[i] = 2; // D
				D.in({location[i], i});
				continue;
			}
		}
			// L R i
			ll ex1 = location[l] + x;
			ll ex2 = location[r] - y;
			if((ex1 == location[0] + D_(0, i) && ex1 > location[r]) && (ex2 < location[l] && D_(0, i) == 2*location[all[0]] - location[0] - ex2)){
				location[i] = ex2;
				stype[i] = 1; // C
				C.in({location[i], i});
				l = i;
			}else if(ex1 == location[0] + D_(0, i) && ex1 > location[r]){
				location[i] = ex1;
				stype[i] = 2; // D
				D.in({location[i], i});
				r = i;
			}else{
				location[i] = ex2;
				stype[i] = 1; // C
				C.in({location[i], i});
				l = i;
			}
	}


	return;

}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:30:5: warning: variable 'mn' set but not used [-Wunused-but-set-variable]
   30 |  ii mn = {1e9, 0};
      |     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98380 KB Output is correct
2 Correct 36 ms 98388 KB Output is correct
3 Correct 35 ms 98388 KB Output is correct
4 Correct 35 ms 98388 KB Output is correct
5 Correct 37 ms 98280 KB Output is correct
6 Correct 35 ms 98312 KB Output is correct
7 Correct 36 ms 98324 KB Output is correct
8 Correct 35 ms 98508 KB Output is correct
9 Correct 36 ms 98392 KB Output is correct
10 Correct 41 ms 98300 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98392 KB Output is correct
2 Correct 36 ms 98388 KB Output is correct
3 Correct 36 ms 98380 KB Output is correct
4 Correct 35 ms 98360 KB Output is correct
5 Correct 35 ms 98324 KB Output is correct
6 Correct 43 ms 98300 KB Output is correct
7 Correct 37 ms 98324 KB Output is correct
8 Correct 36 ms 98356 KB Output is correct
9 Correct 37 ms 98380 KB Output is correct
10 Correct 37 ms 98320 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 98648 KB Output is correct
2 Correct 102 ms 98680 KB Output is correct
3 Correct 105 ms 98676 KB Output is correct
4 Correct 105 ms 98692 KB Output is correct
5 Correct 105 ms 98712 KB Output is correct
6 Correct 108 ms 98688 KB Output is correct
7 Correct 104 ms 98676 KB Output is correct
8 Correct 104 ms 98692 KB Output is correct
9 Correct 113 ms 98680 KB Output is correct
10 Correct 107 ms 98684 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 98644 KB Output is correct
2 Correct 105 ms 98700 KB Output is correct
3 Correct 102 ms 98696 KB Output is correct
4 Correct 104 ms 98680 KB Output is correct
5 Correct 105 ms 98688 KB Output is correct
6 Correct 105 ms 98692 KB Output is correct
7 Correct 105 ms 98680 KB Output is correct
8 Correct 105 ms 98764 KB Output is correct
9 Correct 104 ms 98804 KB Output is correct
10 Correct 107 ms 98684 KB Output is correct
11 Correct 104 ms 98684 KB Output is correct
12 Correct 104 ms 98788 KB Output is correct
13 Correct 105 ms 98736 KB Output is correct
14 Correct 106 ms 98764 KB Output is correct
15 Correct 103 ms 98756 KB Output is correct
16 Correct 105 ms 98692 KB Output is correct
17 Correct 105 ms 98768 KB Output is correct
18 Correct 105 ms 98680 KB Output is correct
19 Correct 106 ms 98768 KB Output is correct
20 Correct 106 ms 98756 KB Output is correct