Submission #990442

#	Time	Username	Problem	Language	Result	Execution time	Memory
990442		AdamGS	Rail (IOI14_rail)	C++17	30 / 100	41 ms	864 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7;
set<int>C, D;
int odl(int a, int b, int x) {
  if(C.find(b)!=C.end() || D.find(b)!=D.end()) return INF;
  if(a<b) {
    if(x==1) {
      auto it=D.lower_bound(b);
      int p=*it;
      return p-a+p-b;
    }
    return b-a;
  }
  auto it=D.lower_bound(a);
  int p=*it;
  if(x==2) {
    auto it=C.lower_bound(b); --it;
    auto q=*it;
    return p-a+p-q+b-q;
  }
  return p-a+p-b;
}
int odl2(int a, int b) {
  if(C.find(b)!=C.end() || D.find(b)!=D.end()) return INF;
  if(a>b) swap(a, b);
  auto it=C.lower_bound(a);
  if(it==C.begin()) return INF;
  --it;
  auto p=*it;
  return a-p+b-p;
}
void findLocation(int n, int first, int location[], int stype[]) {
  location[0]=first;
  stype[0]=1;
  if(n==1) return;
  vector<int>P(n);
  rep(i, n-1) P[i+1]=getDistance(0, i+1);
  vector<pair<int,int>>V;
  rep(i, n-1) V.pb({P[i+1], i+1});
  sort(all(V));
  location[V[0].nd]=location[0]+V[0].st;
  stype[V[0].nd]=2;
  C.insert(location[0]);
  D.insert(location[V[0].nd]);
  int a=0, b=V[0].nd;
  for(int i=1; i<V.size(); ++i) {
    int x=getDistance(V[i].nd, a), y=getDistance(V[i].nd, b);
    if(odl(location[0], location[a]+x, 2)==V[i].st && odl2(location[b], location[a]+x)==y) {
      location[V[i].nd]=location[a]+x;
      stype[V[i].nd]=2;
      D.insert(location[V[i].nd]);
      if(location[V[i].nd]>location[b]) b=V[i].nd;
    } else {
      location[V[i].nd]=location[b]-y;
      stype[V[i].nd]=1;
      C.insert(location[V[i].nd]);
      if(location[V[i].nd]<location[a]) a=V[i].nd;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=1; i<V.size(); ++i) {
      |                ~^~~~~~~~~

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