Submission #301933

#	Time	Username	Problem	Language	Result	Execution time	Memory
301933		peti1234	Rail (IOI14_rail)	C++17	30 / 100	84 ms	504 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int c=5002;
int a[c], b[c], pos=1, js, bs, el, id, x;
vector<pair<int, int> > bal, jobb;
int tav(int a, int b) {
    return getDistance(a, b);
    /*
    cout << a << " " << b << "\n";
    int x; cin >> x;
    return x;
    /*/
}
void findLocation(int n, int first, int location[], int stype[]) {
    for (int i=1; i<n; i++) {
        a[i]=tav(0, i);
        if (a[i]<a[pos]) pos=i;
    }
    location[0]=first, location[pos]=location[0]+a[pos], stype[0]=1, stype[pos]=2;
    for (int i=1; i<n; i++) {
        if (i!=pos) {
            b[i]=tav(pos, i);
            if (a[i]<b[i]) jobb.push_back({a[i], i});
            else bal.push_back({b[i], i});
        }
    }
    sort(jobb.begin(), jobb.end()), sort(bal.begin(), bal.end());
    js=jobb.size(), bs=bal.size();
    if (js) {
        id=jobb[0].second, el=id;
        stype[id]=2, location[id]=location[0]+tav(0, id);
        for (int i=1; i<js; i++) {
            id=jobb[i].second, x=tav(el, id);
            if (a[el]+x==a[id]) stype[id]=1, location[id]=location[el]-x;
            else stype[id]=2, location[id]=location[0]+a[id], el=id;
        }
    }
    if (bs) {
        id=bal[0].second, el=id;
        stype[id]=1, location[id]=location[pos]-tav(pos, id);
        for (int i=1; i<bs; i++) {
            id=bal[i].second, x=tav(el, id);
            if (b[el]+x==b[id]) stype[id]=2, location[id]=location[el]+x;
            else stype[id]=1, location[id]=location[pos]-b[id], el=id;
        }
    }
    //for (int i=0; i<n; i++) cout << location[i] << " " << stype[i] << "\n";
    return;
}

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