Submission #1101893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101893		_8_8_	Rail (IOI14_rail)	C++17	30 / 100	121 ms	99428 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);
}
map<int, vector<int>> id;
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 = 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);
    }
    for(auto [f, vec]:id) {
        for(int j:vec) {
            int val = get(L, R);
            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 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] == 1 && pos[j] < pos[L]) {
                L = j;            
            }
            if(s[j] == 2 && pos[j] > pos[R]) {
                R = j;
            }
        }
        for(int j:vec) {
            if(s[j]) continue;
            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]) {
                            cur = i;
                        }
                    }
                    if(get(R, j) == pos[R] - pos[cur] + mb - pos[cur]) {
                        s[j] = 2;
                        pos[j] = mb;
                    }
                }
            }
            if(!s[j]) {
                int mb = pos[R] - get(R, j);
                int cur = R;
                for(int i = 0; i < n; i++) {
                    if(s[i] == 2 && pos[i] < pos[cur]) {
                        cur = i;
                    }
                }
                if(get(L, j) == pos[cur] - pos[L] + pos[cur] - mb) {
                    s[j] = 1;
                    pos[j] = mb;
                }
            }
            if(s[j] == 1 && pos[j] < pos[L]) {
                L = j;            
            }
            if(s[j] == 2 && pos[j] > pos[R]) {
                R = j;
            }
        }
        // return;
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:36:17: warning: unused variable 'val' [-Wunused-variable]
   36 |             int val = get(L, R);
      |                 ^~~
rail.cpp:26:9: warning: unused variable 'u' [-Wunused-variable]
   26 |     int u = R;
      |         ^

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