Submission #1064173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064173		anango	Rail (IOI14_rail)	C++17	100 / 100	82 ms	884 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define cout cerr

int INF = 1LL<<60;


void findLocation(signed N, signed first, signed location[], signed stype[]) {
    
    int n = N;
    if (n==1) {
        location[0] = first;
        stype[0] = 1;
        return;
    }
    for (int i=0; i<n; i++) {
        stype[i] = -1;
    }
    //query dist from 0 to everywhere and the smallest dist is the first D type after 0
    //and let x = dist between 0 and A (A=first D type after 0
    //immediately we know the value of x and location and type of A
    //so of the remaining n-2 nodes
    //let's say we are trying to find where node i is, i not processed yet
    //let d0 = dist(0,i) and d1 = dist(i,A), note dist is commutative
    //if d0<d1, i is on the right of A
    //otherwise, i is on the left of A
    //if position is in between 0 and A, then we know immediately the location, and it must be C-type
    //since the first D-type after 0 is A
    //since d0>d1 and d1-d0 = x (note that |d1-d0| = x no matter what)
    //now, consider that i is to the right of A (d0<d1)
    //let the 'apparent distance' be the x-coordinate that i would be at if 0 is at 0 and if it was a D-type
    //so apparent distance = d0
    //assume by induction that we've already queried things closer than i to 0
    //thusforely we have the rightmost D type (rightmost station must be D type else it's not connected)
    //and so query the dist from that to our node
    //if this distance is equal to expected (x-coordinate of that plus d0)
    //then our node is D-type, so we know x-coordinate is just d0
    //if not equal to expected, now we know that it's C-type, and we also know the distance to this last D-type node
    //so the real x-coordinate is the x-coordinate of the last D-type node, minus the distance from this node to that
    //similar method on the other side
    //this uses n-1 queries (0 to everywhere else) plus n-2 queries (1 to everywhere else except 0) plus n-2 queries 
    //(1 for each additional node), at most
    //3n-5 is good
    //just assume 0 is stationed at 0 and then add first to everything in the answer
    vector<int> dist0(n,-1);
    dist0[0] = 0;
    for (int i=1; i<n; i++) {
        dist0[i] = getDistance(0,i);
    }

    vector<int> bydist(n,0); iota(bydist.begin(), bydist.end(), (int)0);
    sort(bydist.begin(), bydist.end(),[&](const int i1, const int i2) {
        return dist0[i1]<dist0[i2];
    });

    vector<int> coordinates(n,-1);
    coordinates[0] = 0;
    int A = bydist[1];
    int X = dist0[A];
    coordinates[A] = X;
    int earliestC = 0;
    int latestD = A; 
    stype[0] = 1;
    stype[A] = 2;

    
    
    
    /*cout << "distances " << endl;
    for (int i=0; i<n; i++) {
        cout << "dist " << i <<" " << dist0[i]  << endl;
    }
    cout << "got " << A <<" " << X << endl;*/
    for (int pos=2; pos<n; pos++) {
        int city = bydist[pos];
        int d0 = dist0[city];
        int d1 = getDistance(A,city);
        //cout << "doing " << city <<" " << d0 <<" " << dist_to_earliestC <<" " << dist_to_latestD << " " << pos1 <<" " << pos2 << endl;
        //need to verify if distance to 0 is matching what we think in pos1, then in pos2
        //for pos1, need to find minimum position D such that it's after pos1 and earliest C
        
        if (d0<d1+X) {
            //it's on the right of d1
            int dist_to_latestD = getDistance(latestD,city);
            int posC = coordinates[latestD]-dist_to_latestD;
            int posD = d0;
            //check the first D after this C, if distance from C to that D to 0 is equal to d0 then it's a C
            //the correct coordinate (if it's C) is coordinates[latestD] - dist_to_latestD
            //imagine it's type C
            //where is the next D
            //well, d0 = coordinates[next D]*2 - posC if this is the case
            //so coordinates[next D] = (posC+d0)/2 = ()

            int minposD = INF;
            for (int i=0; i<n; i++) {
                if (stype[i]==2 && coordinates[i]>=max((int)0,posC)) {
                    minposD = min(minposD,coordinates[i]);
                }
            }
            int expected_distance = 2*minposD-posC-0;
            if (expected_distance==d0 && posC>0 && posC<coordinates[latestD]) {
                stype[city] = 1;
                coordinates[city] = posC;
            }
            else {
                stype[city] = 2;
                coordinates[city] = posD;
            }
        }
        else {
            //it's on the left of d1
            int dist_to_earliestC = getDistance(earliestC,city);
            int posC = X-d1;
            int posD = coordinates[earliestC]+dist_to_earliestC;
            int maxposC = -INF;
            for (int i=0; i<n; i++) {
                if (stype[i]==1 && coordinates[i]<=min(posD,(int)X)) {
                    maxposC = max(maxposC,coordinates[i]);
                }
            }
            int expected_distance = (X-maxposC)+(posD-maxposC);
            if (expected_distance==d1 && posD<X && posD>coordinates[earliestC] && (!(0<posD && posD<X))) {
                stype[city] = 2;
                coordinates[city] = posD;
            }
            else {
                stype[city] = 1;
                coordinates[city] = posC;
            }
        }

        if (coordinates[city]<coordinates[earliestC]) earliestC = city;
        if (coordinates[city]>coordinates[latestD]) latestD = city;

    }
    for (int i=0; i<n; i++) {
        location[i] = coordinates[i]+first;
        //cout << i <<" " << coordinates[i] <<" " << stype[i] <<" " << location[i] << endl;
    }
    
    


}

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