Submission #1011886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011886		ProtonDecay314	Rail (IOI14_rail)	C++17	30 / 100	53 ms	828 KiB

rail

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define TCASES int t; cin >> t; while(t--)
// #define DEBUG

#ifndef DEBUG
#include "rail.h"
#endif

#ifdef DEBUG
int getDistance(int i, int j) {
    cout << i << " " << j << endl;

    int ans;
    cin >> ans;
    return ans;
}
#endif

void findLocation(int n, int first, int location[], int stype[]) {
    LI(i, 0, n) stype[i] = 0;
    location[0] = first;
    stype[0] = 1;

    if(n == 1) return; // Special case: if there's only one station, exit

    // Get the distances from station zero
    // Get the minimum distance, that will be a type 2 block
    
    vpi d0;

    d0.push_back({0, 0});
    
    int stx = 0;
    int mindist0 = numeric_limits<int>::max();
    LI(i, 1, n) {
        d0.push_back({getDistance(0, i), i});
        if(d0[i].fi < mindist0) {
            mindist0 = d0[i].fi;
            stx = i;
        }
    }

    location[stx] = first + mindist0;
    stype[stx] = 2;

    vpi d0sorted = d0;

    sort(d0sorted.begin(), d0sorted.end()); 

    // Getting distances from station X

    vpi dx;

    LI(i, 0, n) {
        if(i == stx) {
            dx.push_back({0, i});
            continue;
        }

        dx.push_back({getDistance(stx, i), i});
    }

    // Now we have ((--)
    /*
    (---)--(((--[(--]--)(--))

    (---(--)-)[]
    */

    int sty = stx;
    int styl = 0; // leftmost C-type

    int rightmost_midcase_c = first;

    LI(_i, 0, n) {
        int i = d0sorted[_i].se;

        if(i == 0 || i == stx) continue;
        if(dx[i].fi < dx[0].fi) {
            // Station Z is between 0 and x

            location[i] = first + d0[stx].fi - dx[i].fi;
            stype[i] = 1;

            rightmost_midcase_c = max(rightmost_midcase_c, location[i]);
        } else if(d0[i].fi == dx[i].fi + d0[stx].fi) {
            // Station Z is to the left of 0: literally just mirror the logic below

            int distzy = getDistance(i, styl);
            int deflect_st_block = location[styl] - ((dx[i].fi - dx[styl].fi - distzy) >> 1ll);

            int typeof_dst = 0;

            L(j, 0, n) {
                if(location[j] == deflect_st_block) {
                    typeof_dst = stype[j];
                    break;
                } 
            }

            if(typeof_dst == 1) {
                // Deflector is of C-type, thus, the current station is 
                // of type D

                location[i] = location[styl] + distzy;
                stype[i] = 2;
            } else {
                // Deflector is of D-type or does not exist, thus the current station is of type C

                location[i] = first + dx[0].fi - dx[i].fi;
                stype[i] = 1;
                styl = i;
            }
        } else {
            // Station Z is to the right

            int distzy = getDistance(i, sty);
            int deflect_st_block = location[sty] + ((d0[i].fi - d0[sty].fi - distzy) >> 1ll);

            int typeof_dst = 0;

            L(j, 0, n) {
                if(location[j] == deflect_st_block) {
                    typeof_dst = stype[j];
                    break;
                } 
            }

            if(typeof_dst == 2) {
                // Deflector is of D-type, thus, the current station is 
                // of type C

                location[i] = location[sty] - distzy;
                stype[i] = 1;
            } else {
                // Deflector is of C-type or does not exist, thus the current station is of type D

                location[i] = first + d0[i].fi;
                stype[i] = 2;
                sty = i;
            }
        }
    }

    // ok we're done!
}

#ifdef DEBUG
int main() {
    int n, first;
    cin >> n >> first;

    vi location(n, 0);
    vi stype(n, 0);

    findLocation(n, first, &location[0], &stype[0]);

    cout << "THE ANSWER" << endl;

    L(i, 0, n) {
        cout << i << " " << (stype[i] == 1 ? "C" : "D") << " " << location[i] << endl;
    }
    return 0;
}
#endif

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