oj.uz

Submission #348938

# Submission time Handle Problem Language Result Execution time Memory
348938 2021-01-16T06:03:05 Z talant117408 Rail (IOI14_rail) C++17
100 / 100
 96 ms 4460 KB 
#include "rail.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;
using namespace std;

//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

int occupied[1000007];
int d0[5003], d1[5003];

void findLocation(int n, int zeroth, int location[], int type[]){
    int len = 2e9, ind = 0;
    for(int i = 1; i < n; i++){
        d0[i] = getDistance(0, i);
        if(d0[i] < len){
            len = d0[i];
            ind = i;
        }
    }
    
    location[0] = zeroth;
    type[0] = occupied[zeroth] = 1;
    location[ind] = zeroth+len;
    type[ind] = occupied[zeroth+len] = 2;
    
    for(int i = 0; i < n; i++){
        if(ind != i){
            d1[i] = getDistance(ind, i);
        }
    }
    
    vector <pii> left, right;
    
    for(int i = 1; i < n; i++){
        if(i != ind){
            if(d0[i] == len+d1[i]){
                if(len > d1[i]){
                    location[i] = location[ind]-d1[i];
                    type[i] = occupied[location[i]] = 1;
                }
                else{
                    left.pb(mp(d1[i], i));
                }
            }
            else{
                right.pb(mp(d0[i], i));
            }
        }
    }
    sort(all(left));
    sort(all(right));
    
    int R = ind;
    
    for(auto a : right){
        auto x = a.second;
        auto drx = getDistance(R, x);
        auto gap = (d0[R]+drx-d0[x])/2;
        if(occupied[location[R]-gap] == 1 || occupied[location[R]-gap] == 0){
            location[x] = d0[x]+zeroth;
            type[x] = occupied[location[x]] = 2;
            R = x;
        }
        else{
            location[x] = location[R]-drx;
            type[x] = occupied[location[x]] = 1;
        }
    }
    
    R = 0;
    
    for(auto a : left){
        auto x = a.second;
        auto drx = getDistance(R, x);
        auto gap = (d1[R]+drx-d1[x])/2;
        if(occupied[location[R]+gap]%2 == 0){
            location[x] = location[ind]-d1[x];
            type[x] = occupied[location[x]] = 1;
            R = x;
        }
        else{
            location[x] = location[R]+drx;
            type[x] = occupied[location[x]] = 2;
        }
    }
}
/*
4
6
1 4
2 5
2 10
1 1
1 0
2 2
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4332 KB Output is correct
2 Correct 86 ms 4332 KB Output is correct
3 Correct 85 ms 4460 KB Output is correct
4 Correct 87 ms 4460 KB Output is correct
5 Correct 88 ms 4460 KB Output is correct
6 Correct 86 ms 4204 KB Output is correct
7 Correct 89 ms 4352 KB Output is correct
8 Correct 85 ms 4332 KB Output is correct
9 Correct 86 ms 4332 KB Output is correct
10 Correct 89 ms 4460 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4204 KB Output is correct
2 Correct 85 ms 4332 KB Output is correct
3 Correct 85 ms 4460 KB Output is correct
4 Correct 87 ms 4460 KB Output is correct
5 Correct 86 ms 4332 KB Output is correct
6 Correct 86 ms 4204 KB Output is correct
7 Correct 88 ms 4204 KB Output is correct
8 Correct 86 ms 4332 KB Output is correct
9 Correct 88 ms 4332 KB Output is correct
10 Correct 86 ms 4460 KB Output is correct
11 Correct 85 ms 4204 KB Output is correct
12 Correct 89 ms 4460 KB Output is correct
13 Correct 96 ms 4332 KB Output is correct
14 Correct 87 ms 4460 KB Output is correct
15 Correct 86 ms 4332 KB Output is correct
16 Correct 86 ms 4460 KB Output is correct
17 Correct 86 ms 4460 KB Output is correct
18 Correct 87 ms 4460 KB Output is correct
19 Correct 87 ms 4332 KB Output is correct
20 Correct 86 ms 4460 KB Output is correct