Submission #1027110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027110		boyliguanhan	Rail (IOI14_rail)	C++17	100 / 100	46 ms	1104 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
bitset<1<<20>isthereaD,isthereaC;
int LOC[5010],TYPE[5010];
void toright(vector<pair<int,int>> v,int F,int loc,int locf){
    sort(v.begin(),v.end());
    int y=F,dy=abs(loc-locf),locy=locf;
    isthereaD[locf]=1;
    for(auto [k0,i]:v) {
        int YY=getDistance(y,i);
        int delta=dy+YY-k0;
        delta/=2;
        if(isthereaD[locy-delta]){
            TYPE[i]=1;
            LOC[i]=locy-YY;
        } else {
            TYPE[i]=2;
            LOC[i]=loc+k0;
            locy=LOC[i];
            dy=k0,y=i;
            isthereaD[LOC[i]]=1;
        }
    }
}
void toleft(vector<pair<int,int>> v,int F,int loc,int locf){
    sort(v.begin(),v.end());
    isthereaC[locf]=1;
    int y=F,dy=abs(loc-locf),locy=locf;
    for(auto[k0,i]:v){
        int YY=getDistance(y,i);
        int delta=dy+YY-k0;
        delta/=2;
        if(isthereaC[locy+delta]){
            TYPE[i]=2;
            LOC[i]=loc-dy+YY;
        } else {
            TYPE[i]=1;
            LOC[i]=loc-k0;
            locy=LOC[i];
            dy=k0,y=i;
            isthereaC[LOC[i]]=1;
        }
    }
}
void findLocation(int N, int first, int location[], int stype[]) {
    TYPE[0]=1,LOC[0]=first;
    vector<pair<int,int>> distto0;
    for(int i=1;i<N;i++)
        distto0.push_back({getDistance(i,0),i});
    sort(distto0.begin(),distto0.end());
    auto[L,X]=distto0[0];
    LOC[X]=first+L;
    TYPE[X]=2;
    vector<pair<int,int>>onright,onleft;
    for(int uwu=1;uwu<N-1;uwu++){
        auto [k0,i]=distto0[uwu];
        int kx=getDistance(i,X);
        if(L+kx==k0)
            onleft.push_back({kx,i});
        else onright.push_back({k0,i});
    }
    toright(onright,X,first,LOC[X]);
    toleft(onleft,0,LOC[X],first);
    for(int i=0;i<N;i++)
        location[i]=LOC[i],stype[i]=TYPE[i];
}

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