Submission #1166980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166980		HappyCapybara	Rail (IOI14_rail)	C++20	30 / 100	40 ms	596 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;
    if (N == 1) return;
    vector<int> d1(N, 0), d2(N, 0);
    int csf = pow(10, 7), cs;
    for (int i=1; i<N; i++){
        d1[i] = getDistance(0, i);
        if (d1[i] < csf){
            csf = d1[i];
            cs = i;
        }
    }
    location[cs] = first+d1[cs];
    stype[cs] = 2;
    vector<pair<int,int>> l, r;
    for (int i=1; i<N; i++){
        if (i == cs) continue;
        d2[i] = getDistance(cs, i);
        if (d2[i] > d1[i]) r.push_back({d1[i], i});
        else l.push_back({d2[i], i});
    }
    int lm = 0, rm = cs;
    vector<pair<int,int>> ls, rs;
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());
    for (auto [d, i] : l){
        vector<int> pl;
        for (auto [j, mx] : ls){
            if (d-d2[j] < mx) pl.push_back(location[j]+d-d2[j]);
        }
        int res = getDistance(lm, i);
        bool b = true;
        for (int x : pl){
            if (x == location[lm]+res){
                location[i] = x;
                stype[i] = 2;
                b = false;
                break;
            }
        }
        if (b){
            location[i] = location[cs]-d;
            stype[i] = 1;
            ls.push_back({i, location[lm]-location[i]});
            lm = i;
        }
    }
    for (auto [d, i] : r){
        vector<int> pl;
        for (auto [j, mx] : rs){
            if (d-d1[j] < mx) pl.push_back(location[j]-(d-d1[j]));
        }
        int res = getDistance(rm, i);
        bool b = true;
        for (int x : pl){
            if (x == location[rm]-res){
                location[i] = x;
                stype[i] = 1;
                b = false;
                break;
            }
        }
        if (b){
            location[i] = location[0]+d;
            stype[i] = 2;
            rs.push_back({i, location[i]-location[rm]});
            rm = i;
        }
    }
    //cout << endl;
    //for (int i=0; i<N; i++) cout << stype[i] << " " << location[i] << endl;
    return;
}

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