oj.uz

Submission #96903

# Submission time Handle Problem Language Result Execution time Memory
96903 2019-02-12T17:59:24 Z SecretAgent007 Rail (IOI14_rail) C++17
100 / 100
 177 ms 17992 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
int diste[109][109];

int getDistance(int a, int b){
    return diste[a][b];
}
*/

int memo[5009][5009];

int dist(int a, int b){
    if(memo[a][b]) return memo[a][b];
    return memo[a][b] = getDistance(a,b);
}

void findLocation(int N, int first, int location[], int stype[]){
	stype[0] = 1;
	location[0] = first;
	vector< pair<int, int> > v(0);
	for(int i = 1; i < N; i++){
        v.push_back({dist(0,i), i});
	}
	sort(v.begin(), v.end());
	int second = v[0].second;
	location[second] = first+dist(0,second);
	stype[second] = 2;

    int R = second;
    set< pair<int, int> > r;
    int L = 0;
    set< pair<int, int> > l;
    r.insert(make_pair(location[R], R));
    l.insert(make_pair(location[L], L));
    //cout << L << ' ' << R << endl;
    for(int it = 1; it < N-1; it++){
        int i = v[it].second;
        if(dist(0,i) == dist(0,second)+dist(second,i) && dist(second,i) > dist(0,second)){
            //LEFT
           // cout << "Left " << i << endl;
            int p = location[L]+dist(L,i);
            auto t = lower_bound(l.begin(), l.end(), make_pair(p,0));
            t--;
            auto vale = *t;
            int val = vale.second;
            //cout << p << ' ' << val << endl;
            int d = p-vale.first;
            if(dist(0,second)+dist(second, val)+d == dist(0,i)){
                location[i] = p;
                stype[i] = 2;
            }else{
                stype[i] = 1;
                L = i;
                location[i] = first-(dist(0,i)-2*dist(0,second));
                l.insert(make_pair(location[i],i));
            }
        }else{
            //RIGHT
            //cout << "Right " << i << endl;
            int p = location[R]-dist(R,i);
            //for(auto a : r) cout << a.first << ' ' << a.second << endl;
            auto t = lower_bound(r.begin(), r.end(), make_pair(p,-1));
            auto vale = *t;
            int val = vale.second;
            //cout << p << ' ' << val << endl;
            int d = vale.first-p;
            if(dist(0,i) == dist(0,val)+d){
                location[i] = location[val]-d;
                stype[i] = 1;
            }else{
                R = i;
                stype[i] = 2;
                location[i] = first+dist(0,i);
                r.insert(make_pair(location[i], i));
            }
        }
    }
}
/*
int main(){
    int n;
    cin >> n;
    int first;
    cin >> first;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> diste[i][j];
        }
    }
    int location[n];
    int stype[n];
    for(int i = 0; i < n; i++){
        location[i] = INT_MAX;
        stype[i] = INT_MAX;
    }
    findLocation(n,first, location,stype);
    cout << endl;
    for(int a : location) cout << a << ' ';
    cout << endl;
    for(int a : stype) cout << a << ' ';
    cout << endl;
}
/*
5 4
0 12 4 15 7
12 0 8 3 11
4 8 0 11 3
15 3 11 0 14
7 11 3 14 0
*/

Compilation message

rail.cpp:105:1: warning: "/*" within comment [-Wcomment]
 /*

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 17856 KB Output is correct
2 Correct 160 ms 17912 KB Output is correct
3 Correct 138 ms 17912 KB Output is correct
4 Correct 140 ms 17936 KB Output is correct
5 Correct 154 ms 17752 KB Output is correct
6 Correct 177 ms 17884 KB Output is correct
7 Correct 155 ms 17620 KB Output is correct
8 Correct 138 ms 17756 KB Output is correct
9 Correct 142 ms 17992 KB Output is correct
10 Correct 150 ms 17736 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 17884 KB Output is correct
2 Correct 139 ms 17756 KB Output is correct
3 Correct 147 ms 17884 KB Output is correct
4 Correct 143 ms 17912 KB Output is correct
5 Correct 162 ms 17784 KB Output is correct
6 Correct 176 ms 17912 KB Output is correct
7 Correct 163 ms 17656 KB Output is correct
8 Correct 143 ms 17700 KB Output is correct
9 Correct 145 ms 17788 KB Output is correct
10 Correct 148 ms 17696 KB Output is correct
11 Correct 159 ms 17912 KB Output is correct
12 Correct 157 ms 17784 KB Output is correct
13 Correct 149 ms 17784 KB Output is correct
14 Correct 152 ms 17784 KB Output is correct
15 Correct 154 ms 17784 KB Output is correct
16 Correct 139 ms 17912 KB Output is correct
17 Correct 160 ms 17656 KB Output is correct
18 Correct 146 ms 17884 KB Output is correct
19 Correct 153 ms 17756 KB Output is correct
20 Correct 152 ms 17904 KB Output is correct