Submission #1101875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101875		_8_8_	Rail (IOI14_rail)	C++17	30 / 100	89 ms	98968 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 12;
int mem[N][N];
int get(int i, int j) {
    if(i > j) swap(i, j);
    if(mem[i][j] != -1) return mem[i][j];
    return mem[i][j] = getDistance(i, j);
}
void findLocation(int n, int first, int pos[], int s[]) {
    memset(mem, -1, sizeof(mem));
    for(int i = 0; i < n; i++) {
        s[i] = 0;
    }
    s[0] = 1;
    pos[0] = first;
    int L = 0;
    vector<pair<int, int>> a;
    for(int i = 1; i < n; i++) {
        a.push_back({get(0, i), i});
    }
    sort(a.rbegin(), a.rend());
    int R = a.back().second;
    int u = 0;
    s[R] = 2;
    pos[R] = pos[0] + a.back().first;
    a.pop_back();
    reverse(a.begin(), a.end());
    for(auto [f, j]:a) {
        int val = get(L, R);
        if(get(L, j) > val) {
            int cur = 0;
            for(int j = 0; j < n; j++) {
                if(s[j] == 1 && pos[j] > pos[cur]) {
                    cur = j;
                }
            }
            if(pos[R] - pos[cur] + (pos[L] + get(L,j) - pos[cur]) == get(R, j)) {
                s[j] = 2;
                pos[j] = pos[L] + get(L, j);
            } else {
                s[j] = 1;
                pos[j] = pos[R] - get(R, j);
            }
        } else {
            int mb = get(L, j) + pos[L];
            int cur = L;
            for(int j = 0; j < n; j++) {
                if(s[j] == 1 && pos[j] < mb && pos[j] > pos[cur]) {
                    cur = j;
                }
            }
            if(pos[R] - pos[cur] * 2 + mb == get(R, j)) {
                s[j] = 2;
                pos[j] = mb;
            } else {
                s[j] = 1;
                pos[j] = pos[R] - get(R, j);
            }
        }

        if(s[j] == 1 && pos[j] < pos[L]) {
            L = j;            
        }
        if(s[j] == 2 && pos[j] > pos[R]) {
            R = j;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:25:9: warning: unused variable 'u' [-Wunused-variable]
   25 |     int u = 0;
      |         ^

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