Submission #987409

#	Time	Username	Problem	Language	Result	Execution time	Memory
987409		AlphaMale06	Rail (IOI14_rail)	C++17	30 / 100	100 ms	652 KiB

rail

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

#define F first
#define S second

int getDistance(int x, int y);


void del(vector<pair<int, int>> & x, int el){
    bool ok=0;
    for(int i=0; i< x.size()-1; i++){
        if(x[i].S==el)ok=1;
        if(ok)swap(x[i], x[i+1]);
    }
    x.pop_back();
}

void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    if(n==1)return;
    vector<pair<int, int>> d1;
    for(int i=1; i<n; i++){
        d1.push_back({getDistance(0, i), i});
    }
    sort(d1.begin(), d1.end());
    int sec = d1[0].S;
    location[sec]=first+d1[0].F;
    stype[sec]=2;
    vector<pair<int, int>> d2;
    for(int i=1; i<n; i++){
        if(i!=sec){
            d2.push_back({getDistance(sec, i), i});
        }
    }
    sort(d2.begin(), d2.end());
    del(d1, sec);
    if(n==2)return;
    int trd;
    if(d1[0].F<d2[0].F){
        trd=d1[0].S;
        location[trd]=location[0]+d1[0].F;
        stype[trd]=2;
    }
    else{
        trd=d2[0].S;
        location[trd]=location[sec]-d2[0].F;
        stype[trd]=1;
    }
    del(d1, trd);
    del(d2, trd);
    if(n==3)return;
    int cur = trd;
    for(int i=3; i<n; i++){
        int dist;
        if(stype[cur]==1)dist=getDistance(cur, d1[0].S);
        else dist=getDistance(cur, d2[0].S);
        int mn=min({dist, d1[0].F, d2[0].F});
        int nw=0, nwloc, nwtp;
        if(mn==dist){
            if(stype[cur]==1){
                nw=d1[0].S;
                nwloc = location[cur]+dist;
                nwtp = 2;
            }
            else{
                nw=d2[0].S;
                nwloc = location[cur]-dist;
                nwtp = 1;
            }
        }
        else if(mn==d1[0].F){
            nwtp=2;
            nwloc=location[0]+d1[0].F;
            nw=d1[0].S;
        }
        else{
            nwtp=1;
            nwloc=location[sec]-d2[0].F;
            nw=d2[0].S;
        }
        location[nw]=nwloc;
        stype[nw]=nwtp;
        cur=nw;
        del(d1, nw);
        del(d2, nw);
    }
}

Compilation message (stderr)

rail.cpp: In function 'void del(std::vector<std::pair<int, int> >&, int)':
rail.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0; i< x.size()-1; i++){
      |                  ~^~~~~~~~~~~~

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