Submission #795655

#	Time	Username	Problem	Language	Result	Execution time	Memory
795655		medmdg	Rail (IOI14_rail)	C++14	30 / 100	44 ms	512 KiB

rail

#include <bits/stdc++.h>
#pragma once
#include "rail.h"
using ll =long long;
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
 
using namespace std;
 
int minind(vi &v){
    int mn=v[0];
    int m=0;
    for(int i=1;i<v.size();i++){
        if(v[i]<mn){
            mn=v[i];
            m=i;
        }
    }
    return m;
}
 
int getDistance(int i, int j);
void findLocation(int n, int first, int location[], int stype[]){
    for(int i=0;i<n;i++){
        location[i]=0;
        stype[i]=0;
    }
    vi d0(n),ds(n);
    for(int i=1;i<n;i++){
        d0[i]= getDistance(0,i);
    }
    d0[0]=INF;
    int second=minind(d0);
    d0[0]=0;
    for(int i=1;i<n;i++){
        if(i==second)continue;
        int dist= getDistance(i,second);
        ds[i]=dist;
    }
    stype[0]=1;
    stype[second]=2;
    location[0]=first;
    location[second]=first+d0[second];
    vector<pi>right,left;
    for(int i=0;i<n;i++){
        if(stype[i])continue;
        if(d0[i]>ds[i]){
            left.push_back(make_pair(ds[i],i));
        }
        else right.push_back(make_pair(d0[i],i));
    }
    std::sort(right.begin(), right.end());
    std::sort(left.begin(), left.end());
    int last=second,lasto=0;
    for(auto p:right){
        int i=p.second;
        int dist= getDistance(i,last);
        if(dist!=(d0[i]-location[lasto]+first)+location[last]-location[lasto]){
            stype[i]=1;
            location[i]= location[last]-dist;
          if(location[i]>location[lasto])
          lasto=i;
        }
        else{
            stype[i]=2;
            location[i]=first+d0[i];
            last=i;
        }
    }
  	if(left.size()){
    last =  left[0].second;
  	stype[last]=1;
  	location[last]=location[second]-ds[last];
    }
    lasto=second;
    for( auto p:left){
        int i=p.second;
      	if(i==last)continue;
        int dist= getDistance(i,last);
        if(ds[i]+location[lasto]-location[second]-location[last]+location[lasto]!=dist){
            stype[i]=2;
            location[i]=location[last]+dist;
          if(location[i]<location[lasto])
          lasto=i;
        }
        else {
            stype[i]=1;
            location[i]=location[second]-ds[i];
            last=i;
        }
    }
 
}

Compilation message (stderr)

rail.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~
rail.cpp: In function 'int minind(std::vector<int>&)':
rail.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=1;i<v.size();i++){
      |                 ~^~~~~~~~~

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