Submission #581534

#	Time	Username	Problem	Language	Result	Execution time	Memory
581534		jasmin	Rail (IOI14_rail)	C++17	8 / 100	323 ms	98576 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int inf=1e9;
vector<int> location, stype;

/*int getDistance(int a, int b){
    cout << "getDist: " << a << " " << b << "\n" << flush;
    int ans;
    cin >> ans;
    return ans;
}*/

void findLocation(signed n, signed first, signed location[], signed stype[]){
    location[0]=first;
    stype[0]=1;
    if(n==1) return;

    vector<vector<int> > dist(n, vector<int> (n, inf));
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            dist[i][j]=dist[j][i]=getDistance(i, j);
        }
    }

    vector<int> closest(n);
    for(int i=0; i<n; i++){
        int best=-1; int mini=inf;
        for(int j=0; j<n; j++){
            if(j==i) continue;
            int d=dist[i][j];
            if(d<mini){
                best=j;
                mini=d;
            }
        }
        closest[i]=best;
    }
    int a=closest[0];

    for(int i=1; i<n; i++){
        int d0=dist[0][i];
        int da=dist[a][i];

        if(d0<da){

            int dclose=dist[0][closest[i]];
            int dclose2=dist[0][closest[closest[i]]];
            if(dclose2<dclose){
                stype[i]=2;
                location[i]=first+d0;
            }
            else{
                stype[i]=1;
                location[i]=first+d0-(2*dist[i][closest[i]]);
            }
        }
        else{

            int dclose=dist[0][closest[i]];
            int dclose2=dist[0][closest[closest[i]]];
            
            if(dclose<dclose2){
                stype[i]=1;
                location[i]=first-(d0-2*(dist[0][a])-2*(dist[i][closest[i]]));
            }
            else{
                stype[i]=1;
                location[i]=first-(d0-(2*dist[0][a]));
            }
        }
    }
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int first;
    cin >> first;
    location.assign(n, 0);
    stype.assign(n, 0);
    findLocation(n, first, location, stype);
    for(int i=0; i<n; i++){
        cout << location[i] << " " << stype[i] << "\n";
    }
}*/

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