Submission #1008046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008046		hotboy2703	Rail (IOI14_rail)	C++14	100 / 100	49 ms	912 KiB

rail

#include "rail.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace{
    const ll MAXN = 5e3+5;
    ll n;
    ll dist0[MAXN];
    ll dista[MAXN];
    ll a;
}
void findLocation(int N, int first, int location[], int stype[])
{
    map< ll,ll> mp;
    location[0] = first,stype[0] = 1;
    mp[location[0]] = 1;
    if (n==1){
        return;
    }
    n = N;
    for (ll i = 1;i < n;i ++){
        dist0[i] = getDistance(0,i);
    }

    a = 1;
    for (ll i = 1;i < n;i ++){
        if (dist0[i] < dist0[a])a=i;
    }
    location[a] = location[0] + dist0[a];
    stype[a] = 2;
    mp[location[a]] = 2;
//    cout<<a<<' '<<location[a]<<'\n';
    for (ll  i = 1;i < n;i ++){
        if (i != a)dista[i] = getDistance(a,i);
    }
    dista[0] = dist0[a];
    vector <ll> all0,alla;
    for (ll i = 1;i < n;i ++){
        if (i != a){
            if (dist0[i] != dista[i] + dist0[a])all0.push_back(i);
            else alla.push_back(i);
        }
    }
    sort(all0.begin(),all0.end(),[&](ll x,ll y){return dist0[x] < dist0[y];});
//    map <ll,ll> mp;
    for (ll i = 0;i < sz(all0);i ++){
        ll j = i;
        location[all0[i]] = dist0[all0[i]]+location[0];
        stype[all0[i]] = 2;
        mp[location[all0[i]]] = 2;
        while (j + 1 < sz(all0)){
            ll dick = getDistance(all0[i],all0[j+1]);
//            if (all0[j+1]==6){
//                cout<<dist0[all0[i]]<<' '<<dick<<' '<<dist0[all0[j+1]]<<'\n';
//            }
            if (dist0[all0[i]] + dick == dist0[all0[j+1]] || mp[location[all0[i]] - (dist0[all0[i]] + dick - dist0[all0[j+1]])/2] == 2){
                j++;
                location[all0[j]] = location[all0[i]] - dick;
                stype[all0[j]] = 1;
                mp[location[all0[j]]] = 1;
            }
            else{
                break;
            }
        }
        i = j;
    }
//    alla.push_back(0);
    sort(alla.begin(),alla.end(),[&](ll x,ll y){return dista[x] < dista[y];});
//    for (auto x:alla)cout<<x<<' ';
//    cout<<'\n';
    for (ll i = 0;i < sz(alla);i ++){
//        cout<<alla[i]<<'\n';
        ll j = i;
        location[alla[i]] = -dista[alla[i]]+location[a];
        stype[alla[i]] = 1;
        mp[location[alla[i]]] = 1;
//        cout<<alla[i]<<'\n';
        while (j + 1 < sz(alla)){

            ll dick = getDistance(alla[i],alla[j+1]);
//            cout<<alla[i]<<' '<<alla[j+1]<<' '<<dick<<' '<<location[alla[i]] + (dist0[alla[i]] + dick - dist0[alla[j+1]])/2<<'\n';
            if (dista[alla[i]] + dick == dista[alla[j+1]] || mp[location[alla[i]] + (dista[alla[i]] + dick - dista[alla[j+1]])/2] == 1){
                j++;
                location[alla[j]] = location[alla[i]] + dick;
                stype[alla[j]] = 2;
                mp[location[alla[j]]] = 2;
            }
            else{
                break;
            }
        }
        i = j;
    }
//    for (ll j = 0;j < n; j++){
//        cout<<stype[j]<<' '<<location[j]<<'\n';
//    }
}

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