Submission #69233

#	Time	Username	Problem	Language	Result	Execution time	Memory
69233		edisonhello	Rail (IOI14_rail)	C++14	30 / 100	101 ms	820 KiB

rail

#include<bits/stdc++.h>
using namespace std;
int disf0[5005],disfo[5005];

#ifdef WEAK
int getDistance(int i,int j){
    cout<<"Q "<<i<<" "<<j<<endl;
    int t; cin>>t; return t;
}
#else
#include"rail.h"
#endif

#define get getDistance
void findLocation(int n,int first,int location[],int stype[]){
    for(int i=1;i<n;++i)disf0[i]=get(0,i);
    int o=min_element(disf0+1,disf0+n)-disf0; 
    stype[0]=1; stype[o]=2;
    location[o]=disf0[o];
    for(int i=1;i<n;++i)if(i!=o)disfo[i]=get(o,i);
    vector<int> L,R;
    for(int i=1;i<n;++i)if(i!=o){
        if(disfo[i]<disf0[o])location[i]=location[o]-disfo[i],stype[i]=1;
        else if(disf0[i]<disfo[i])R.push_back(i);
        else L.push_back(i);
    }
    {
        sort(L.begin(),L.end(),[&](const int &a,const int &b){ return disfo[a]<disfo[b]; });
        int la=0;
        for(int i:L){
            int d=get(i,la);
            if(d==disfo[i]-disfo[la])location[i]=location[la]+d,stype[i]=2;
            else location[i]=location[o]-disfo[i],stype[i]=1,la=i;
        }
    }
    {
        sort(R.begin(),R.end(),[&](const int &a,const int &b){ return disf0[a]<disf0[b]; });
        int la=o;
        for(int i:R){
            int d=get(i,la);
            if(d==disf0[i]-disf0[la])location[i]=location[la]-d,stype[i]=1;
            else location[i]=location[0]+disf0[i],stype[i]=2,la=i;
        }
    }

    for(int i=0;i<n;++i)location[i]+=first;

}

#ifdef WEAK
int lo[4152454],st[2555554];
int main(){
    int n=4;

    findLocation(n,2,lo,st);

    cout<<"location: "; for(int i=0;i<n;++i)cout<<lo[i]<<" "; cout<<endl;
    cout<<"stype: "; for(int i=0;i<n;++i)cout<<st[i]<<" "; cout<<endl;
}
#endif

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