Submission #1011950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011950		ProtonDecay314	Rail (IOI14_rail)	C++17	100 / 100	52 ms	652 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
// #define AUTO_INTERACTOR

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

int n;
#ifdef DEBUG
vi a_loc;
vi a_type;

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

    int ans;

    int loc_i = a_loc[i], loc_j = a_loc[j];
    if(loc_i > loc_j) {
        swap(loc_i, loc_j);
        swap(i, j);
    }

    // Now, i is to the left of j
    int typei = a_type[i], typej = a_type[j];
    if(typei == 1 && typej == 2) {
        ans = loc_j - loc_i;
    } else if (typei == 1 && typej == 1) {
        // Find the leftmost D that is to the right of both

        int leftmost_d_pos = numeric_limits<int>::max();

        LI(_i, 0, n) {
            if(a_loc[_i] > loc_j && a_type[_i] == 2 && a_loc[_i] < leftmost_d_pos) leftmost_d_pos = a_loc[_i];
        }

        ans = (leftmost_d_pos << 1) - (loc_i + loc_j);
    } else if(typei == 2 && typej == 2) {
        // Find the rightmost C that is to the left of both

        int rightmost_c_pos = numeric_limits<int>::min();

        LI(_i, 0, n) {
            if(a_loc[_i] < loc_i && a_type[_i] == 1 && a_loc[_i] > rightmost_c_pos) rightmost_c_pos = a_loc[_i];
        }
        ans = (loc_i + loc_j) - (rightmost_c_pos << 1);
    } else {
        int leftmost_d_pos = numeric_limits<int>::max();
        int rightmost_c_pos = numeric_limits<int>::min();

        LI(_i, 0, n) {
            if(a_loc[_i] > loc_j && a_type[_i] == 2 && a_loc[_i] < leftmost_d_pos) leftmost_d_pos = a_loc[_i];
            if(a_loc[_i] < loc_i && a_type[_i] == 1 && a_loc[_i] > rightmost_c_pos) rightmost_c_pos = a_loc[_i];
        }

        ans = ((rightmost_c_pos - leftmost_d_pos) << 1) - (loc_j - loc_i);
    }
    cout << ans << endl;
    return ans;
    #endif
    #ifndef AUTO_INTERACTOR
    cout << i << " " << j << endl;
    int ans;
    cin >> ans;
    return ans;
    #endif
}
#endif

void findLocation(int n, int first, int location[], int stype[]) {
    LI(i, 0, n) {stype[i] = 0; location[i] = -1;}
    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

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

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

            location[i] = first + d0[stx].fi - dx[i].fi;
            stype[i] = 1;
            #ifdef DEBUG
            cout << "MIDCASE " << i << endl;
            #endif

        } 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) >> 1);

            int typeof_dst = 0;

            LI(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, 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) >> 1);

            int typeof_dst = 0;

            LI(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, 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() {
    cin >> n;
    #ifndef AUTO_INTERACTOR
    int first;
    cin >> first;
    #endif
    

    #ifdef AUTO_INTERACTOR
    LI(i, 0, n) {
        char c; int loc;
        cin >> c >> loc;

        a_type.push_back(c == 'C' ? 1 : 2);
        a_loc.push_back(loc);
    }
    #endif

    #ifdef AUTO_INTERACTOR
    int first = a_loc[0];
    #endif

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

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

    cout << "THE ANSWER" << endl;

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

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