Submission #581365

#	Time	Username	Problem	Language	Result	Execution time	Memory
581365		Josia	Rail (IOI14_rail)	C++14	30 / 100	74 ms	468 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

void findLocation(int N, int first, int location[], int stype[]) {
    vector<bool> visited(N);

    location[0] = 0;
    stype[0] = 1;
    visited[0] = 1;
    vector<int> distancesFromZero;
    for (int i=0; i<N; i++) {
        if (i == 0) {
            distancesFromZero.push_back(1e9); continue;
        }
        distancesFromZero.push_back(getDistance(0, i));
    }

    int nextRight = min_element(distancesFromZero.begin(), distancesFromZero.end())-distancesFromZero.begin();
    stype[nextRight] = 2;
    location[nextRight] = distancesFromZero[nextRight];
    visited[nextRight] = 1;

    
    vector<int> distancesFromNextRight;
    for (int i=0; i<N; i++) {
        if (i == nextRight) {
            distancesFromNextRight.push_back(1e9); continue;
        }
        distancesFromNextRight.push_back(getDistance(nextRight, i));
    }


    // for (int i = 0; i<N; i++) {
    //     cerr << distancesFromZero[i] << " ";
    // }
    // cerr << "\n";
    // for (int i = 0; i<N; i++) {
    //     cerr << distancesFromNextRight[i] << " ";
    // }
    // cerr << "\n";
    // cerr << "\n";


    for (int i=0; i<N; i++) {
        if (visited[i]) continue;
        if (distancesFromZero[nextRight] + distancesFromNextRight[i] == distancesFromZero[i]) {
            stype[i] = 1;
            location[i] = location[nextRight]-distancesFromNextRight[i];
            visited[i] = 1;
        }

        if (distancesFromZero[i] + distancesFromZero[nextRight] == distancesFromNextRight[i]) {
            stype[i] = 2;
            location[i] = distancesFromZero[i];
            visited[i] = 1;
        }
    }
















    for (int i = 0; i<N; i++) {
        location[i] += first;
        // cerr << location[i] << " ";
    }
    // cerr << "\n";
    // for (int i = 0; i<N; i++) cerr << stype[i] << " ";
    // cerr << "\n";
}

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