Submission #391733

#	Time	Username	Problem	Language	Result	Execution time	Memory
391733		Aldas25	Rail (IOI14_rail)	C++14	8 / 100	90 ms	504 KiB

rail

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;

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

    vii seq;
    FOR(i, 1, n-1) {
        int d = getDistance(0, i);
        seq.pb({d, i});
    }

    sort(seq.begin(), seq.end());

    int le = 0, ri = seq[0].s;
    stype[ri] = 2;
    location[ri] = first + seq[0].f;

    FOR(i, 1, (int)seq.size()-1) {
        int id = seq[i].s;
        int d1 = getDistance(le, id);
        int d2 = getDistance(ri, id);
        if (d1 < d2) {
            location[id] = location[le] + d1;
            stype[id] = 2;
        } else {
            location[id] = location[ri] - d2;
            stype[id] = 1;
        }
        if (location[id] < location[le]) le = id;
        if (location[id] > location[ri]) ri = id;
    }

    /*FOR(i, 0, n-1) {
        cout << " i = " << i << " location = " << location[i] << " stype = " << stype[i] << endl;
    }*/

}

/*

1
4
1 1
2 4
2 7
2 9


2
6
1 3
2 6
2 7
1 1
1 0
2 8



*/

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