Submission #1102038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102038		_8_8_	Rail (IOI14_rail)	C++17	100 / 100	105 ms	99560 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 12;


int mem[N][N], c =0 ;
int get(int i, int j) {
    if(i == j) return 0;
    if(i > j) swap(i, j);
    if(mem[i][j] != -1) return mem[i][j];
    c++;
    return mem[i][j] = getDistance(i, j);
}
map<int, vector<int>> id;
void findLocation(int32_t n, int32_t first, int32_t pos[], int32_t 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 = R;
    s[R] = 2;
    pos[R] = pos[0] + a.back().first;
    a.pop_back();
    reverse(a.begin(), a.end());
    for(auto [f, j]:a) {
        id[f].push_back(j);
    }
    int prev = c;
    for(auto [f, vec]:id) {
        for(int j:vec) {
            if(!s[j]) {
                int mb = pos[R] - get(R, j);
                if(mb > pos[L]) {
                    int cur = R;
                    for(int i = 0; i < n; i++) {
                        if(s[i] == 2 && pos[i] < pos[cur] && pos[i] > mb) {
                            cur = i;
                        }
                    }
                    if(get(L, j) == pos[cur] * 2 - pos[L] - mb) {
                        s[j] = 1;
                        pos[j] = mb;
                    }
                }
            }
            if(!s[j]) {
                int mb = pos[L] + get(L, j);
                if(mb < pos[R]) {
                    int cur = L;
                    for(int i = 0; i < n; i++) {
                        if(s[i] == 1 && pos[i] > pos[cur] && pos[i] < mb) {
                            cur = i;
                        }
                    }
                    if(get(R, j) == pos[R] - pos[cur] + mb - pos[cur]) {
                        s[j] = 2;
                        pos[j] = mb;
                    }
                }
            }
            if(!s[j]) {
                int y = get(R, j);
                int mb = pos[R] - y;
                if(get(0, j) == pos[u] - pos[0] + pos[u] - mb) {
                    pos[j] = mb;
                    s[j] = 1;
                } else {
                    pos[j] = pos[L] + get(L, j);
                    s[j] = 2;
                }
            }
            if(s[j] == 1 && pos[j] < pos[L]) {
                L = j;            
            }
            if(s[j] == 2 && pos[j] > pos[R]) {
                R = j;
            }
        }
        prev = c;
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int32_t, int32_t, int32_t*, int32_t*)':
rail.cpp:38:9: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
   38 |     int prev = c;
      |         ^~~~

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