Submission #1102168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102168		alexander707070	Rail (IOI14_rail)	C++14	30 / 100	56 ms	2708 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"

#define MAXN 1000007
using namespace std;

const int inf=1e7;

int n,pos,fr;
pair<int,int> block[MAXN];
pair<int,int> dist[5007];
int last;

vector<int> clos,opos;
int sum[MAXN];

int loc[MAXN];
vector< pair<int,int> > know;

int distan(int x,int y,int xx,int yy){
    if(y!=yy){
        if(y==1 and yy==2){
            if(x<xx)return xx-x;
            
            pair<int,int> news={inf,0};
            for(pair<int,int> s:know){
                if(s.first>x and s.second==2 and s.first<news.first){
                    news=s;
                }
            }

            return distan(news.first,news.second,xx,yy)+abs(news.first-x);
        }else{
            if(x>xx)return x-xx;
            
            pair<int,int> news={-2,0};
            for(pair<int,int> s:know){
                if(s.first<x and s.second==1 and s.first>news.first){
                    news=s;
                }
            }

            return distan(news.first,news.second,xx,yy)+abs(news.first-x);
        }
    }else{
        if(y==1 and yy==1){
            if(x>xx)swap(x,xx);

            pair<int,int> news={inf,0};
            for(pair<int,int> s:know){
                if(s.first>xx and s.second==2 and s.first<news.first){
                    news=s;
                }
            }

            return distan(news.first,news.second,xx,yy)+abs(news.first-x);
        }else{
            if(x>xx)swap(x,xx);

            pair<int,int> news={-2,0};
            for(pair<int,int> s:know){
                if(s.first<x and s.second==1 and s.first>news.first){
                    news=s;
                }
            }

            return distan(news.first,news.second,xx,yy)+abs(news.first-x);
        }
    }
}

bool check(int pos,int st,int d1,int d2){

    int s1=distan(pos,st,loc[dist[last].second],2);
    int s2=distan(pos,st,loc[dist[fr].second],1);

    return s1==d1 and s2==d2;
}

void findLocation(int N, int first, int location[], int stype[]){
    n=N;

    loc[0]=first;
    stype[0]=1;
    know.push_back({first,1});

    for(int i=1;i<n;i++){
        dist[i].first=getDistance(0,i);
        dist[i].second=i;
    }

    sort(dist+1,dist+n);

    last=1; fr=0;
    loc[dist[1].second]=first+dist[1].first;
    stype[dist[1].second]=2;

    know.push_back({loc[dist[1].second],2});

    clos.push_back(1);
    opos.push_back(0);

    for(int i=2;i<n;i++){

        int curr=getDistance(dist[i].second,dist[last].second);
        int where=loc[dist[last].second]-curr;

        int curr2=getDistance(dist[i].second,dist[fr].second);
        int where2=loc[dist[fr].second]+curr2;
        
        if(check(where,1,curr,curr2)){
            loc[dist[i].second]=where;
            stype[dist[i].second]=1;
        }else if(true){
            loc[dist[i].second]=where2;
            stype[dist[i].second]=2;
        }else{
            cout<<"failed\n";
        }

        if(loc[dist[i].second]>loc[dist[last].second]){
            last=i;
            clos.push_back(i);
        }

        if(loc[dist[i].second]<loc[dist[fr].second]){
            fr=i;
            opos.push_back(i);
        }

        know.push_back({loc[dist[i].second],stype[dist[i].second]});
    }

    for(int i=0;i<n;i++){
        location[i]=loc[i];
    }

    return;
}

/*
3
8
1 0
2 2
1 3
2 5
2 6
1 7
1 8
2 10


*/

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