Submission #391754

#	Time	Username	Problem	Language	Result	Execution time	Memory
391754		Aldas25	Rail (IOI14_rail)	C++14	30 / 100	274 ms	532 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;

const int MAXN = 5100;

int n;
int pos[MAXN], st[MAXN];

int calcD (int fr, int to) {
    bool wasSw = false;
    if (st[fr] == 2) {
        FOR(i, 0, n-1) {
            pos[i] *= -1;
            st[i] = 1+2 - st[i];
        }
        wasSw = true;
    }

    int ret = 0;

    /// assuming st[fr] = 1
    if (st[to] == 2) {
        if (pos[to] >= pos[fr]) ret = pos[to] - pos[fr];
        else {
            ret = 0;
            int ch = -1;
            FOR(i, 0, n-1) {
                if (st[i] != 2) continue;
                if (pos[i] < pos[fr]) continue;
                if (ch == -1 || pos[i] < pos[ch]) ch = i;
            }
            ret += pos[ch] - pos[fr];
            int ch2 = -1;
            FOR(i, 0, n-1) {
                if (st[i] != 1) continue;
                if (pos[i] > pos[to]) continue;
                if (ch2 == -1 || pos[i] > pos[ch2]) ch2 = i;
            }
            ret += pos[ch] - pos[ch2];
            ret += pos[to] - pos[ch2];
        }
    } else {
        int ch = -1;
        FOR(i, 0, n-1) {
            if (st[i] != 2) continue;
            if (pos[i] < pos[fr]) continue;
            if (pos[i] < pos[to]) continue;
            if (ch == -1 || pos[i] < pos[ch]) ch = i;
        }
        ret = pos[ch] - pos[fr];
        ret += pos[ch] - pos[to];
        //return ret;
    }

    if (wasSw) {
        FOR(i, 0, n-1) {
            pos[i] *= -1;
            st[i] = 1+2 - st[i];
        }
    }

    return ret;
}


void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    pos[0] = first;
    st[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;
    st[ri] = 2;
    pos[ri] = first + seq[0].f;

    FOR(i, 1, (int)seq.size()-1) {
        int id = seq[i].s;
        int d0 = seq[i].f;
        int d1 = getDistance(id, le);
        int d2 = getDistance(id, ri);

        pos[id] = pos[le] + d1;
        st[id] = 2;

        if (calcD (0, id) != d0 || calcD(id, ri) != d2) {
            pos[id] = pos[ri] - d2;
            st[id] = 1;
        }

        if (pos[id] < pos[le] && st[id] == 1) le = id;
        if (pos[id] > pos[ri] && st[id] == 2) ri = id;
    }

    FOR(i, 0, n-1) {
        location[i] = pos[i];
        stype[i] = st[i];
    }

    /*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: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44