Submission #691754

#	Time	Username	Problem	Language	Result	Execution time	Memory
691754		Khizri	Rail (IOI14_rail)	C++17	30 / 100	3066 ms	52492 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=5000+5;
int dp[mxn][mxn],color[mxn],dis[mxn],st[mxn],pos[mxn],mx,l,r;
set<int>x,y;
int ask(int i,int j){
    if(pos[i]!=-1&&pos[j]!=-1&&st[i]+st[j]==3){
        return abs(pos[i]-pos[j]);
    }
    if(i>j) swap(i,j);
    if(i==j) return 0;
    if(dp[i][j]) return dp[i][j];
    return dp[i][j]=getDistance(i,j);
}
bool check1(int i){
    int nw=pos[r]-ask(r,i);
    auto it=y.lower_bound(pos[l]);
    int m=*it;
    //if(i==2) cout<<m<<' '<<pos[l]<<' '<<pos[r]<<' '<<nw<<endl;
    //if(i==2) cout<<ask(l,i)<<endl;
    if(ask(l,i)==abs(pos[l]-m)+abs(m-nw)){
        pos[i]=nw;
        st[i]=1;
        x.insert(pos[i]);
        l=i;
        return true;
    }
    else{
        if(i==2){
            //OK;
        }
        return false;
    }
}
bool check2(int i){
    auto it=x.upper_bound(pos[r]);
    it--;
    int m=*it;
    int nw=pos[l]+ask(l,i);
    if(ask(r,i)==abs(pos[r]-m)+abs(m-nw)){
        pos[i]=nw;
        st[i]=2;
        y.insert(pos[i]);
        r=i;
        return true;
    }
    else{
        return false;
    }
}
bool check3(int i){
    int nw=pos[r]-ask(r,i);
    auto it=y.lower_bound(nw);
    int m=*it;
    if(ask(l,i)==abs(nw-m)+abs(m-pos[l])){
        pos[i]=nw;
        st[i]=1;
        x.insert(pos[i]);
        return true;
    }
    else{
        return false;
    }
}
bool check4(int i){
    int nw=pos[l]+ask(l,i);
    auto it=x.upper_bound(nw);
    it--;
    int m=*it;
    if(ask(r,i)==abs(pos[r]-m)+abs(m-nw)){
        pos[i]=nw;
        st[i]=2;
        y.insert(pos[i]);
        return true;
    }
    else{
        return false;
    }
}
void findLocation(int n, int first, int loc[], int stype[])
{
    for(int i=0;i<n;i++){
        st[i]=-1;
        pos[i]=-1;
    }
    mx=1e5,r=0;
    for(int i=1;i<n;i++){
        if(ask(0,i)<mx){
            mx=ask(0,i);
            r=i;
        }
    }
    l=0;
    pos[0]=first;
    st[0]=1;
    pos[r]=first+mx;
    st[r]=2;
    color[l]=1;
    color[r]=1;
    x.insert(pos[l]);
    y.insert(pos[r]);
    vector<pii>vt;
    for(int i=0;i<n;i++){
        vt.pb({ask(0,i),i});
    }
    sort(all(vt));
    int cnt=n-2;
    while(cnt){
        for(int id=0;id<n;id++){
            int i=vt[id].S;
            if(color[i]){
                continue;
            }
            //cout<<i<<endl;
            if(check1(i)){
                color[i]=1;
                cnt--;
            }
            else if(check2(i)){
                color[i]=1;
                cnt--;
            }
            else if(check3(i)){
                color[i]=1;
                cnt--;
            }
            else if(check4(i)){
                color[i]=1;
                cnt--;
            }
        }
    }
    //cout<<endl;
    for(int i=0;i<n;i++){
        //cout<<st[i]<<' '<<pos[i]<<endl;
        loc[i]=pos[i];
        stype[i]=st[i];
    }
}
/*
4
8
1 7
1 1
2 3
1 5
2 9
2 10
1 12
2 14

4
9
1 1
1 8
2 9
1 10
1 11
2 15
1 7
2 5
1 6

4
11
1 25
1 3
1 5
2 10
2 20
2 21
1 7
2 30
2 40
1 41
2 42
*/

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