Submission #835246

#	Time	Username	Problem	Language	Result	Execution time	Memory
835246		HollaFoil	Rail (IOI14_rail)	C++14	30 / 100	61 ms	34636 KiB

rail

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

using namespace std;
#define maxN 10002
// Distance from house 0;
vector<int> sorted;
int L;
int R;
int locations[maxN];
int types[maxN];
int d[maxN][maxN];
int f;
int s;
int sIndex;
set<int> CLocs;
set<int> DLocs;
int guess = -1;

bool cmp(int i, int j) {
    return d[0][i] < d[0][j];
}

// Case 1:
// L       ?     T    R  
// (       (     )    )
bool test1(int index) {
    guess = locations[R] - d[index][R];
    if (guess < 0) return false;
    int intermediateForL = guess + (d[L][index] - (guess - locations[L]))/2;
    if (DLocs.find(intermediateForL) == DLocs.end()) return false;
    int intermediateForFirst = guess + (d[0][index] - (guess - f))/2;
    if (DLocs.find(intermediateForFirst) == DLocs.end()) return false;
    return true;
}

// Case 2:
// ?   L          T   R  
// (   (          )   )
bool test2(int index) {
    guess = locations[R] - d[index][R];
    if (guess < 0) return false;
    int intermediateForL = guess + (d[L][index] - (guess - locations[L]))/2;
    if (DLocs.find(intermediateForL) == DLocs.end()) return false;
    int intermediateForFirst = guess + (d[0][index] - (guess - f))/2;
    if (DLocs.find(intermediateForFirst) == DLocs.end()) return false;
    return true;
}


// Case 3:
// L     T    ?       R  
// (     (    )       )
bool test3(int index) {
    guess = locations[L] + d[index][L];
    int intermediateForR = guess + (d[R][index] - (locations[R] - guess))/2;
    if (CLocs.find(intermediateForR) == DLocs.end()) return false;
    
    if (guess > f) {
        if (d[0][index] != guess-f) return false;
    }
    else {
        d[sIndex][index] = d[index][sIndex] = d[0][index] - d[0][sIndex];
        int intermediateForSecond = guess + (d[sIndex][index] - (s - guess))/2;
        if (CLocs.find(intermediateForSecond) == CLocs.end()) return false;
    }
    return true;
}
// Case 4:
// L       T       R  ?
// (       (       )  )
bool test4(int index) {
    guess = locations[L] + d[index][L];
    if (guess > 1000000) return false;
    int intermediateForR = guess + (d[R][index] - (locations[R] - guess))/2;
    if (CLocs.find(intermediateForR) == DLocs.end()) return false;
    
    if (guess > f) {
        if (d[0][index] != guess-f) return false;
    }
    else {
        d[sIndex][index] = d[index][sIndex] = d[0][index] - d[0][sIndex];
        int intermediateForSecond = guess + (d[sIndex][index] - (s - guess))/2;
        if (CLocs.find(intermediateForSecond) == CLocs.end()) return false;
    }
    return true;
}

void findLocation(int N, int first, int location[], int stype[]) {
    for (int i = 1; i < N; i++) {
        d[0][i] = d[i][0] = getDistance(0, i);
        sorted.push_back(i);
    }
    sort(sorted.begin(), sorted.end(), cmp);
    int index = sorted[0];
    L = 0;
    R = index;
    locations[0] = first;
    locations[index] = first + d[0][index];
    types[0] = 1;
    types[index] = 2;
    CLocs.insert(first);
    DLocs.insert(locations[index]);
    f = first;
    s = locations[index];
    sIndex = index;


    for (int i = 1; i < sorted.size(); i++) {
        index = sorted[i];
        d[L][index] = d[index][L] = getDistance(L, index);
        d[R][index] = d[index][R] = getDistance(R, index);
        if (test1(index)) {
            locations[index] = guess;
            types[index] = 1;
        }
        else if (test2(index)) {
            locations[index] = guess;
            types[index] = 1;
        }
        else if (test3(index)) {
            locations[index] = guess;
            types[index] = 2;
        }
        else if (test4(index)) {
            locations[index] = guess;
            types[index] = 2;
        }
        if (locations[index] > locations[R]) R = index;
        if (locations[index] < locations[L]) L = index;
    }

    for (int i = 0; i < N; i++) {
        location[i] = locations[i];
        stype[i] = types[i];
    }

}


/*
Track left most (, right most ).
Sort from stop 0 by distance (stop 0 is '(');

Have to discern 4 cases. Let T be 
a potential intermediary turn stop

Case 1:

L       ?     T    R  
(       (     )    )

If we have d[?][R] be a one way trip, 
then d[?][] = d[L][T] + d[T][?], and 
T must be a node we have seen


Case 2:

?   L          T   R  
(   (          )   )

If we have d[?][R] be a one way trip, 
then d[?][] = d[L][T] + d[T][?], and 
T must be a node we have seen

Case 3:

L     T    ?       R  
(     (    )       )

Case 4:

L       T       R  ?
(       (       )  )
2 6
1 5
1 3
1 1
2 7
2 9
2 11


*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 1; i < sorted.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

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