Submission #793042

#	Time	Username	Problem	Language	Result	Execution time	Memory
793042		Ronin13	Rail (IOI14_rail)	C++17	30 / 100	49 ms	3340 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 1000000;
int val[nmax];

void findLocation(int N, int first, int location[], int stype[])
{
    int n = N;
    array<int, 2> a[n];
    for(int i = 0; i < n; i++){
        a[i][0] =getDistance(0, i);
        a[i][1] = i;
    }
    sort(a, a + n);
    int l = 0, r = a[1][1];
    stype[r] = 2;
    stype[l] = 1;
    //cout << r;
    location[r] = first + a[1][0];
    location[0] = first;
    val[first + a[1][0]] = 2;
    val[first] = 1;
    for(int i= 2; i < n; i++){
        //
        int ind = a[i][1];
        int d1 = getDistance(l, ind);
        int d2 = getDistance(r, ind);
        //cout << d1 << ' ' << d2 << "\n";
        //cout << location[r] << "\n";
        if(location[l] + d1 < location[r]){
            int p = location[l] + location[r] - d1 - d2;
            if(p % 2 == 0){
                p /= 2;
                if(val[p] == 1){
                    location[ind] = location[l] + d1;
                    val[location[ind]] = 2;
                    stype[ind] = 2;
                    continue;
                }
            }
        }
        if(location[l] + d1 > location[r]){
            int p = location[l] + location[r] + d1 - d2;
            
            if(p % 2 == 0){
                p /= 2;
                //cout << p << ' ' << val[p] << "\n";
                if(val[p] == 1){
                    location[ind] = location[l] + d1;
                    val[location[ind]] = 2;
                    stype[ind] = 2;
                    r = ind;
                    continue;
                }
            }
        }
        stype[ind] = 1;
        location[ind] = location[r] - d2;
       // cout << location[ind] << ' ';
        val[location[ind]] = 1;
        if(location[r] - d2 < location[l])
            l = ind;
    }
}

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