Submission #673369

#	Time	Username	Problem	Language	Result	Execution time	Memory
673369		1bin	Rail (IOI14_rail)	C++14	100 / 100	68 ms	644 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
 
using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
 
/*
int getDistance(int a, int b){
    cout << a << ' ' << b << endl;
    int x;
    cin >> x;
    return x;
}*/

void findLocation(int n, int fi, int location[], int stype[]){
    vector<pair<int, int>> v;
    set<int> L, R;
    
    for(int i = 1; i < n; i++){
        int d = getDistance(0, i);
        v.emplace_back(d, i);
    }
    sort(all(v));
    location[0] = fi; stype[0] = 1;
    if(n == 1) return;
    
    auto [d0, t] = v[0];
    location[t] = fi + d0; stype[t] = 2;
    int l, r;
    l = 0, r = t;
    for(int i = 1; i < n - 1; i++){
        auto&[d, x] = v[i];
        int d1 = getDistance(t, x);
        if(d0 + d1 == d){
            int xl = getDistance(x, l);
            if(l && L.find(-d + fi + location[l] + 2 * d0 + xl) != L.end()){
                location[x] = location[l] + xl;
                stype[x] = 2;
            }
            else{
                location[x] = fi + 2 * d0 - d;
                stype[x] = 1;
                if(location[x] < fi) l = x, L.emplace(location[x] * 2);
            }
        }
        else{
            int xr = getDistance(r, x);
            if(r != t && R.find(d + fi + location[r] - xr) != R.end()){
                location[x] = location[r] - xr;
                stype[x] = 1;
            }
            else{
                location[x] = fi + d;
                stype[x] = 2;
                r = x;
                R.emplace(location[x] * 2);
            }
        }
    }
    return;
}
 
/*
int main(void){
    int n = 4, fi = 2, a[4], b[4];
    findLocation(n, fi, a, b);
    for(int i = 0; i < 4; i++) cout << a[i] << ' ' << b[i] << '\n';
    return 0;
}*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     auto [d0, t] = v[0];
      |          ^
rail.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         auto&[d, x] = v[i];
      |              ^

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