Submission #541560

#	Time	Username	Problem	Language	Result	Execution time	Memory
541560		dxz05	Rail (IOI14_rail)	C++14	100 / 100	95 ms	736 KiB

rail

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

using namespace std;

void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;

    vector<int> dist(N);
    for (int i = 1; i < N; i++) dist[i] = getDistance(0, i);

    vector<int> perm(N - 1);
    iota(perm.begin(), perm.end(), 1);

    sort(perm.begin(), perm.end(), [&](int i, int j){
        return dist[i] < dist[j];
    });
    
    int P = perm[0];
    perm.erase(perm.begin());

    location[P] = first + dist[P];
    stype[P] = 2;
    map<int, int> id = {make_pair(location[0], 0), make_pair(location[P], P)};

    int L = 0, R = P;
    for (int i : perm){
        int dL = getDistance(i, L), dR = getDistance(i, R);

        int p = (location[L] + location[R] + dL - dR) / 2;

        if (id.find(p) == id.end() && p > first || id.find(p) != id.end() && stype[id[p]] == 1){
            location[i] = location[L] + dL;
            stype[i] = 2;
            if (location[i] > location[R]) R = i;
        } else {
            location[i] = location[R] - dR;
            stype[i] = 1;
            if (location[i] < location[L]) L = i;
        }

        id[location[i]] = i;
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:33:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |         if (id.find(p) == id.end() && p > first || id.find(p) != id.end() && stype[id[p]] == 1){
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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