Submission #1062987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062987		anango	Rail (IOI14_rail)	C++17	30 / 100	142 ms	976 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;
    
    vector<int> dist1(n,-1);
    for (int i=0; i<n; i++) {
        if (i==0) dist1[i] = X;
        else if (i==A) dist1[i] = 0;
        else dist1[i] = getDistance(A,i);
    }

    for (int pos=2; pos<n; pos++) {
        int city = bydist[pos];
        int d0 = dist0[city];
        int d1 = dist1[city];
        cout << "doing " << city <<" " << d0 <<" " << d1 << endl;
        assert(abs(d0-d1)==X);
        if (d0>d1) {
            //on the left of A...
            //check if it's between 0 and A
            if (d1<=X) {
                coordinates[city] = pos-d1;
                stype[city] = 1;    //must be type C, since A is the first type D after 0
                continue;
            }
            int apparent_position = -(d1-X);
            int dist_to_earliestC = getDistance(earliestC,city);
            int expected_answer = INF; //if it was actually C type, what would the answer be?
            //need to find the minimum coordinate D that comes after the apparent position, and then get the distance
            int minposD = INF;
            for (int i=0; i<n; i++) {
                if (stype[i]==2 && coordinates[i]>=max(apparent_position,coordinates[earliestC])) {
                    minposD = min(minposD,coordinates[i]);
                }
            }
            expected_answer = (minposD-coordinates[earliestC])+(minposD-apparent_position);
            if (expected_answer==dist_to_earliestC) {
                //it's C-type, and the expected position is correct
                stype[city] = 1;
                coordinates[city] = apparent_position;
                assert(apparent_position<coordinates[earliestC]); //this must be before the previous earliest known C
                earliestC = city;
                //since increasing order of distance
                //else, something must have jambloated
            }
            else {
                //it's D-type, and we use the distance we just got to calculate the new position
                stype[city] = 2;
                coordinates[city] = coordinates[earliestC]+dist_to_earliestC;
            }
        }
        else {
            //on the right of A...
            int apparent_position = d0;
            int dist_to_latestD = getDistance(latestD,city);
            int expected_answer = INF; //if it was actually D type, what would the answer be?
            //need to find the maximum coordinate C that comes before the apparent position, and then get the distance
            int maxposC = -INF;
            for (int i=0; i<n; i++) {
                if (stype[i]==1 && coordinates[i]<=min(apparent_position,coordinates[latestD])) {
                    maxposC = max(maxposC,coordinates[i]);
                }
            }
            expected_answer = (coordinates[latestD]-maxposC)+(apparent_position-maxposC);
            cout << "checking " << coordinates[latestD] <<" " << dist_to_latestD <<" " << maxposC <<" " << expected_answer << endl;
            if (expected_answer==dist_to_latestD) {
                //it's D-type, and the expected position is correct
                stype[city] = 2;
                coordinates[city] = apparent_position;
                assert(apparent_position>coordinates[latestD]); //this must be after the previous latest known D
                latestD = city;
                //since increasing order of distance
                //else, something must have jambloated
            }
            else {
                //it's C-type, and we use the distance we just got to calculate the new position
                stype[city] = 1;
                coordinates[city] = coordinates[latestD]-dist_to_latestD;
            }
        }
    }
    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: 0 / 26
• Subtask 4: 0 / 44