Submission #593771

#	Time	Username	Problem	Language	Result	Execution time	Memory
593771		alirezasamimi100	Rail (IOI14_rail)	C++17	30 / 100	73 ms	3344 KiB

rail

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

#define pb push_back
#define F first
#define S second

using namespace std;

using pii = pair<int, int>;

int n, l, r, tt[1000000];
vector<pii> vec;

void findLocation(int N, int first, int location[], int stype[])
{
  n = N;
  l = 0;
  location[0] = first;
  stype[0] = 1;
  for(int i = 1; i < n; i++){
    vec.pb({getDistance(0, i), i});
  }
  sort(vec.begin(), vec.end());
  if(n == 1) return;
  int p;
  for(p=0; p<n-1; p++){
  	r = vec[p].S;
  	location[r] = location[l] + vec[p].F;
  	stype[r] = 1;
    if(getDistance(r,l)==vec[p].F){
      stype[r]=2;
      tt[location[r]]=1;
      break;
    }
  }
  for(int i = p+1; i < n - 1; i++){
    int k = vec[i].S;
    int x = location[l] + getDistance(l, k), y = location[r] - getDistance(r, k);
    int m = (x + y) >> 1;
    if(tt[m]){
      location[k] = y;
      tt[y] = stype[k] = 0;
      if(y < location[l]) l = k;
    }else{
      location[k] = x;
      tt[x] = stype[k] = 1;
      if(y > location[r]) r = k;
    }
    stype[k]++;
  }
}

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