Submission #593853

#	Time	Username	Problem	Language	Result	Execution time	Memory
593853		alirezasamimi100	Rail (IOI14_rail)	C++17	100 / 100	83 ms	4616 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

using pii = pair<int, int>;

int n, l, r, tt[1000000];
vector<pii> vec;

void findLocation(int N, int first, int location[], int stype[])
{
    memset(tt,-1,sizeof tt);
    n = N;
    l = 0;
    location[0] = first;
    stype[0] = 1;
    for(int i = 1; i < n; i++){
        vec.pb({getDistance(0, i), i});
    }
    sort(vec.begin(), vec.end());
    if(n == 1) return;
    r = vec[0].S;
    location[r] = location[l] + vec[0].F;
    tt[location[r]] = 1;
    stype[r] = 2;
    for(int i = 1; i < n - 1; i++){
        int k = vec[i].S;
        int x = location[l] + getDistance(l, k), y = location[r] - getDistance(r, k);
        int m = (x + y) >> 1;
        if(tt[m] == -1){
            if(m >= location[0]) tt[m] = 0;
            else tt[m] = 1;
        }
        if(tt[m]){
            location[k] = y;
            tt[y] = stype[k] = 0;
            if(y < location[l]) l = k;
        }else{
            location[k] = x;
            tt[x] = stype[k] = 1;
            if(x > location[r]) r = k;
        }
        stype[k]++;
    }
}

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