Submission #1063631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063631		ArthuroWich	Rail (IOI14_rail)	C++17	30 / 100	139 ms	2908 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int dist[5005][5005];
int query(int i, int j) {
    if (dist[i][j]) {
        return dist[i][j];
    }
    dist[i][j] = getDistance(i, j);
    return dist[i][j];
}
void findLocation(int n, int f, int loc[], int st[]) {
    int l = 0, r, l0, r0;
    loc[0] = f;
    st[0] = 1;
    if (n == 1) {
        return;
    }
    vector<pair<int, int>> ord;
    for (int i = 1; i < n; i++) {
        loc[i] = -1;
        ord.push_back({query(0, i), i});
    }
    sort(ord.rbegin(), ord.rend());
    r = ord.back().second;
    loc[r] = loc[0]+ord.back().first;
    st[r] = 2;
    ord.pop_back();
    while(!ord.empty()) {
        auto [_, ind] = ord.back();
        ord.pop_back();
        int ld = query(l, ind), rd = query(r, ind), m1, m2, m3, m4, a;
        //cout << ind << " " << loc[l] << " " << loc[r] << " " << ld << " " << rd << endl;
        m1 = loc[l]+ld; // assume D type
        a = loc[l];
        bool f1 = 0, f2 = 0, f3 = 0, f4 = 0;
        for (int i = 0; i < n; i++) {
            if (loc[l] < loc[i] && loc[i] < m1 && st[i] == 1) {
                a = max(a, loc[i]);
            }
        }
        if (a != -1 && m1 < loc[r] && rd == abs(loc[r]-a)+abs(a-m1)) {
            f1 = 1;
        }
        m2 = loc[r]-rd; // assume C type
        a = loc[r];
        for (int i = 0; i < n; i++) {
            if (m2 < loc[i] && loc[i] < loc[r] && st[i] == 2) {
                a = min(a, loc[i]);
            } 
        }
        if (a != -1 && m2 > loc[l] && ld == abs(loc[l]-a)+abs(a-m2)) {
            f2 = 1;
        }
        m3 = loc[l]+ld; // assume D type, out of range
        a = loc[l];
        for (int i = 0; i < n; i++) {
            if (loc[l] < loc[i] && m3 <= 1000000 && m3 > loc[r] && loc[i] < loc[r] && st[i] == 1) {
                a = max(a, loc[i]);
            }
        }
        if (a != -1 && rd == abs(loc[r]-a)+abs(a-m3)) {
            f3 = 1;
        }
        m4 = loc[r]-rd; // assume C type, out of range
        a = loc[r];
        for (int i = 0; i < n; i++) {
            if (loc[l] < loc[i] && loc[i] < loc[r] && st[i] == 2) {
                a = min(a, loc[i]);
            }
        }
        if (a != -1 && m4 >= 0 && m4 < loc[l] && ld == abs(loc[l]-a)+abs(a-m4)) {
            f4 = 1;
        }
        //cout << f1 << " " << f2 << " " << f3 << " " << f4 << endl;
        //cout << m1 << " " << m2 << " " << m3 << " " << m4 << endl;
        if (f3) {
            loc[ind] = m3;
            st[ind] = 2;
            r = ind;
        } else if (f4) {
            loc[ind] = m4;
            st[ind] = 1;
            l = ind;
        } else if (f1) {
            loc[ind] = m1;
            st[ind] = 2;
        } else if (f2) {
            loc[ind] = m2;
            st[ind] = 1;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:13:19: warning: unused variable 'l0' [-Wunused-variable]
   13 |     int l = 0, r, l0, r0;
      |                   ^~
rail.cpp:13:23: warning: unused variable 'r0' [-Wunused-variable]
   13 |     int l = 0, r, l0, r0;
      |                       ^~

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