Submission #348484

#	Time	Username	Problem	Language	Result	Execution time	Memory
348484		talant117408	Rail (IOI14_rail)	C++17	30 / 100	86 ms	768 KiB

rail

#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;

void findLocation(int n, int loc, int location[], int stype[]){
    set <pii> Cs, Ds;
    vector <pii> v;
    int firstD;
    
    location[0] = loc;
    stype[0] = 1;
    Cs.insert(mp(loc, 0));
    
    for(int i = 1; i < n; i++){
        v.pb(mp(getDistance(0, i), i));
    }
    
    sort(rall(v));
    
    firstD = v.back().second;
    
    location[firstD] = v.back().first+loc;
    stype[firstD] = 2;
    Ds.insert(mp(location[firstD], firstD));
    
    v.pop_back();
    
    while(sz(v)){
        auto it = v.back();
        v.pop_back();
        auto ddd = getDistance(firstD, it.second);
        if(ddd > it.first){
            location[it.second] = it.first+loc;
            stype[it.second] = 2;
            Ds.insert(mp(location[it.second], it.second));
        }
        else{
            auto assumed_loc = location[firstD]-(it.first-(location[firstD]-loc));
            auto to = *Cs.lb(mp(assumed_loc, 0));
            ddd = getDistance(to.second, it.second);
            if(ddd == to.first-assumed_loc){
                location[it.second] = to.first+ddd;
                stype[it.second] = 2;
                Ds.insert(mp(location[it.second], it.second));
            }
            else{
                location[it.second] = assumed_loc;
                stype[it.second] = 1;
                Cs.insert(mp(location[it.second], it.second));
            }
        }
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44