Submission #1264809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264809		duck_luck	Rail (IOI14_rail)	C++20	8 / 100	40 ms	4680 KiB

rail

#include <bits/stdc++.h>

#include "rail.h"

#define F first
#define S second

using namespace std;

constexpr int m = 1e6;
vector<int> typeOnBlock(m);

void C(int n, int& c, int& d, int dn, int location[], int stype[]){
    location[n] = location[d] - dn;
    stype[n] = 1; // C
    typeOnBlock.at(location[n]) = stype[n];
    
    if(dn > d - c) c = n;
}
void D(int n, int& c, int& d, int cn, int location[], int stype[]){
    location[n] = location[c] + cn;
    stype[n] = 2; // D
    typeOnBlock.at(location[n]) = stype[n];

    if(cn > d - c) d = n;
}

void findLocation(int N, int first, int location[], int stype[])
{
            // id, distance
    vector<pair<int, int>> v(N - 1);
    for(int i = 1; i < N; ++i) v.at(i - 1) = {i, getDistance(0, i)};

    sort(v.begin(), v.end(), [](const auto& a, const auto& b){
        return a.S < b.S;
    });

    int c = 0;
    location[c] = first;
    stype[c] = 1;
    typeOnBlock.at(location[c]) = stype[c];

    int d = v.at(0).F;
    location[d] = location[c] + v.at(0).S;
    stype[d] = 2;
    typeOnBlock.at(location[d]) = stype[d];

    for(int i = 1; i < v.size(); ++i){
        int n = v.at(i).F;
        int cn = getDistance(c, n);
        int dn = getDistance(d, n);

        if(cn < dn) D(n, c, d, cn, location, stype);
        else if(cn > dn) C(n, c, d, dn, location, stype);
        else{
            // int cd = getDistance(c, d);
            // int nc = getDistance(n, c);

            // if(cd + dn == nc)

            int mid = (location[d] + location[c]) / 2;
            if(typeOnBlock.at(mid) == 2) C(n, c, d, dn, location, stype);
            else D(n, c, d, cn, location, stype);


            // int type = 0;
            // for(int j = i - 1; j >=0; --j) if(v.at(j).F == mid) type = stype[v.at(j).F];

            // if(type == 1){
            //     location[v.at(i).F] = location[c] + cn;
            //     stype[v.at(i).F] = 2; // D

            //     if(cn > d - c) d = v.at(i).F;
            // }
            // else{
            //     location[v.at(i).F] = location[d] - dn;
            //     stype[v.at(i).F] = 1; // C
                
            //     if(dn > d - c) c = v.at(i).F;
            // }
        }
    }

    return;
}

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