Submission #1134735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134735		Ak_16	Rail (IOI14_rail)	C++17	30 / 100	33 ms	580 KiB

rail

#include <iostream>
#include <vector>
#include <algorithm>
#include "rail.h"
using namespace std;

int dis1[10000];
int sp;
int dis2[10000];
int sta[10000];
int mnd;


struct pla{
  int x, y;
};

vector<pla> lef;
vector<pla> rig;

bool cmp1(const pla &a, const pla &b){
  return a.y > b.y;
}

bool cmp2(const pla &a, const pla &b){
  return a.y < b.y;
}

int getDistance(int i, int j);


void findLocation(int n, int first, int location[], int stype[]){
  location[0] = first;
  stype[0]=1;
  sp = 0;
  sta[0] = 2;
  mnd = 100000000;
  
  
  for(int i=1; i<n; i++){
    dis1[i] = getDistance(0, i);
    if(dis1[i]<mnd){sp = i; mnd = dis1[i];}
  }
  
  location[sp] = first + dis1[sp];
  stype[sp]=2;
  sta[sp] = 2;
  
  
  
  mnd = 100000000;
  
  for(int i=1; i<n; i++){
    if(i!=sp){
      
      dis2[i] = getDistance(sp, i);
      
      if(dis1[i] == dis2[i] + dis1[sp]){
        if(dis2[i]<dis1[sp]){sta[i] = 2; location[i] = location[sp] - dis2[i]; stype[i] = 1;}
        else {sta[i] = 1;}
      }
      else {sta[i] = 3;}
      
    }
  }
  
  
  for(int i=1; i<n; i++){
    if(sta[i]==1){
      lef.push_back({i, dis2[i]});
    }
    if(sta[i]==3){
      rig.push_back({i, dis1[i]});
    }
  }
  
  sort(rig.begin(), rig.end(), cmp1);
  sort(lef.begin(), lef.end(), cmp1);
  int cur = sp;
  
  for(const auto &inf : rig){
    int n1 = inf.x;
    int n2 = inf.y;
    
    if(cur==sp){
      location[n1] = first + n2;
      stype[n1] = 2;
      cur = n1;
    }
    
    else {
      
      int n3 = getDistance(cur, n1);
      
      if(n2 == n3 + dis1[cur]){
        
        location[n1] = location[cur] - n3;
        stype[n1] = 1;
        
      }
      
      else {
        
        location[n1] = first + n2;
        stype[n1] = 2;
        cur = n1;
        
      }
      
    }
  }
  
  cur = 0;
  
  for(const auto &inf : lef){
    int n1 = inf.x;
    int n2 = inf.y;
    
    if(cur==0){
      location[n1] = location[sp] - n2;
      stype[n1] = 1;
      cur = n1;
    }
    
    else {
      
      int n3 = getDistance(cur, n1);
      
      if(n2 == n3 + dis1[cur]){
        
        location[n1] = location[cur] + n3;
        stype[n1] = 2;
        
      }
      
      else {
        
        location[n1] = location[sp] - n2;
        stype[n1] = 1;
        cur = n1;
        
      }
      
    }
  }
  
}

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