oj.uz

Submission #282608

# Submission time Handle Problem Language Result Execution time Memory
282608 2020-08-24T15:44:16 Z shayan_p Rail (IOI14_rail) C++14
100 / 100
 117 ms 2460 KB 
#include<bits/stdc++.h>
#include "rail.h"

#define F first
#define S second
#define sz(s) (int(s.size()))
#define PB push_back
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int A[maxn], B[maxn];

map<pii, int> mp;
int ask(int a, int b){
    if(a == b)
	return 0;
    if(mp.count({a, b}))
	return mp[{a, b}];
    return mp[{a, b}] = mp[{b, a}] = getDistance(a, b);
}

void findLocation(int n, int p, int location[], int stype[]){
    fill(stype, stype + n, -1);
    
    stype[0] = 1;
    location[0] = p;
    if(n == 1)
	return;
    int mnid = 1;
    for(int i = 1; i < n; i++){
	A[i] = ask(0, i);
	if(A[mnid] > A[i])
	    mnid = i;
    }
    stype[mnid] = 2;
    location[mnid] = location[0] + A[mnid];

    int Lid = 0, Rid = mnid, Mid = Lid;
    for(int i = 0; i < n; i++){
	if(i != Lid && i != Rid){
	    B[i] = ask(Rid, i);
	    if(abs(A[i] - B[i]) == location[Rid] - location[Lid] && B[i] < A[i] && B[i] < location[Rid] - location[Lid]){
		stype[i] = 1;
		location[i] = location[Rid] - B[i];
		if(Mid == Lid || B[Mid] > B[i])
		    Mid = i;
	    }		
	}
    }
    vector<pii> L, R;
    for(int i = 0; i < n; i++){
	if(stype[i] == -1){
	    if(abs(A[i] - B[i]) != location[Rid] - location[Lid] || A[i] < B[i])
		R.PB({A[i] - (location[Rid] - location[Lid]), i});
	    else
		L.PB({B[i] - (location[Rid] - location[Lid]), i});		
	}
    }

    {
	vector<pii> dis;
	sort(L.begin(), L.end());
	for(pii p : L){
	    vector<int> candid;
	    for(int i = 0; i < sz(dis); i++){
		if(dis[i].F >= p.F)
		    continue;
		int bk = dis[i].F - (p.F - dis[i].F);
		if(i == 0 && bk <= 0)
		    continue;
		if(i != 0 && dis[i-1].F >= bk)
		    continue;
		candid.PB(bk);
	    }
	    if(sz(candid)){
		int num = ask(dis.back().S, p.S);
		int bk = dis.back().F - num;
		bool any = 0;
		for(int x : candid)
		    any|= bk == x;
		candid.clear();
		if(any)
		    candid.PB(bk);
	    }
	    if(sz(candid)){
		int bk = candid.back();
		location[p.S] = location[Lid] - bk;
		stype[p.S] = 2;
	    }
	    else{
		dis.PB(p);
		location[p.S] = location[Lid] - p.F;
		stype[p.S] = 1;
	    }
	}
    }

    {
	vector<pii> dis;
	sort(R.begin(), R.end());
	for(pii p : R){
	    vector<int> candid;
	    for(int i = 0; i < sz(dis); i++){
		if(dis[i].F >= p.F)
		    continue;
		int bk = dis[i].F - (p.F - dis[i].F);
		if(i == 0 && bk <= 0)
		    continue;
		if(i != 0 && dis[i-1].F >= bk)
		    continue;
		candid.PB(bk);
	    }
	    if(sz(candid)){
		int num = ask(dis.back().S, p.S);
		int bk = dis.back().F - num;
		bool any = 0;
		for(int x : candid)
		    any|= bk == x;
		candid.clear();
		if(any)
		    candid.PB(bk);
	    }
	    if(sz(candid)){
		int bk = candid.back();
		location[p.S] = location[Rid] + bk;
		stype[p.S] = 1;
	    }
	    else{
		dis.PB(p);
		location[p.S] = location[Rid] + p.F;
		stype[p.S] = 2;
	    }
	}
    }
}

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 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 512 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 103 ms 2296 KB Output is correct
2 Correct 102 ms 2296 KB Output is correct
3 Correct 104 ms 2296 KB Output is correct
4 Correct 100 ms 2296 KB Output is correct
5 Correct 106 ms 2424 KB Output is correct
6 Correct 106 ms 2376 KB Output is correct
7 Correct 105 ms 2396 KB Output is correct
8 Correct 105 ms 2388 KB Output is correct
9 Correct 101 ms 2300 KB Output is correct
10 Correct 104 ms 2296 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2388 KB Output is correct
2 Correct 105 ms 2296 KB Output is correct
3 Correct 102 ms 2296 KB Output is correct
4 Correct 106 ms 2396 KB Output is correct
5 Correct 104 ms 2424 KB Output is correct
6 Correct 115 ms 2296 KB Output is correct
7 Correct 106 ms 2296 KB Output is correct
8 Correct 104 ms 2424 KB Output is correct
9 Correct 101 ms 2460 KB Output is correct
10 Correct 111 ms 2392 KB Output is correct
11 Correct 117 ms 2296 KB Output is correct
12 Correct 109 ms 2424 KB Output is correct
13 Correct 102 ms 2388 KB Output is correct
14 Correct 109 ms 2296 KB Output is correct
15 Correct 102 ms 2296 KB Output is correct
16 Correct 101 ms 2296 KB Output is correct
17 Correct 104 ms 2424 KB Output is correct
18 Correct 105 ms 2296 KB Output is correct
19 Correct 104 ms 2380 KB Output is correct
20 Correct 102 ms 2424 KB Output is correct