Submission #911432

#	Time	Username	Problem	Language	Result	Execution time	Memory
911432		mircea_007	Rail (IOI14_rail)	C++17	30 / 100	46 ms	604 KiB

rail

#include "rail.h"

#include <algorithm>
#include <vector>
#include <set>

#include <cassert>

//#include <stdio.h>

const int MAXN = 5000;

const int C = 1;
const int D = 2;

struct Station {
  int type, x;

  Station( int type, int x ): type( type ), x( x ) {}
};

struct Railway {
  std::set<int> Cs;
  std::set<int> Ds;

  void push( Station S ) {
    if( S.type == C )
      Cs.insert( S.x );
    else // D
      Ds.insert( S.x );
  }

  void pop( Station S ) {
    if( S.type == C )
      Cs.erase( S.x );
    else // D
      Ds.erase( S.x );
  }

  int dist( Station A, Station B ) { // station A and B might not be inserted yet
    if( A.x > B.x )
      return dist( B, A );

    // A -?--> B
    int ret = 0, left, right;
    
    if( A.type == D ){
      auto it = Cs.upper_bound( A.x );
      assert( it != Cs.begin() );
      it--;

      left = *it; // vrem un C < A.x
      ret += A.x - left;
    }else
      left = A.x;

    if( B.type == C ){
      auto it = Ds.lower_bound( B.x );
      assert( it != Ds.end() );

      right = *it; // vrem un D > B.x
      ret += right - B.x;
    }else
      right = B.x;

    ret += right - left;

    return ret;
  }

  bool can_insert( Station S, Station R1, int d1, Station R2, int d2, Station R3, int d3 ) {
    push( S );

    bool ret = true;

    ret &= (dist( S, R1 ) == d1);
    ret &= (dist( S, R2 ) == d2);
    ret &= (dist( S, R3 ) == d3);

    // printf( "%d %d %d\n", dist( S, R1 ) == d1, dist( S, R2 ) == d2, dist( S, R3 ) == d3 );

    pop( S );

    return ret;
  }
};

struct Solver {
  int n;
  int first;
  int *loc;
  int *stype;

  void pass_param( int _n, int _first, int *_loc, int *_stype ) {
    n = _n;
    first = _first;
    loc = _loc;
    stype = _stype;

    for( int i = 0 ; i < n ; i++ )
      stype[i] = loc[i] = 0;
  }

  int dist0[MAXN];

  void solve() {
    loc[0] = first;
    stype[0] = C;

    std::vector<int> ord;
    for( int i = 1 ; i < n ; i++ ){
      dist0[i] = getDistance( 0, i );
      ord.push_back( i );
    }

    std::sort( ord.begin(), ord.end(), [this]( int a, int b ) -> bool {
      return dist0[a] < dist0[b];
    } );

    int leftmost = 0;
    int rightmost = ord.front();

    // place data
    loc[rightmost] = first + dist0[rightmost];
    stype[rightmost] = D;

    Railway rail;
    rail.push( Station( C, loc[leftmost] ) );
    rail.push( Station( D, loc[rightmost] ) );
    
    for( int i = 1 ; i < (int)ord.size() ; i++ ){
      int dl = getDistance( leftmost, ord[i] );
      int dr = getDistance( rightmost, ord[i] );
      int d0 = dist0[ord[i]];

      // cases are:
      // L0(R | L)0R | (LR | LR)

      Station var[2] = {
        Station( C, loc[rightmost] - dr ),
        Station( D, loc[leftmost] + dl ),
      };

      Station LM( C, loc[leftmost] );
      Station RM( D, loc[rightmost] );
      Station IN( C, first );

      int idx = 0;
      while( idx < 2 && !rail.can_insert( var[idx], LM, dl, RM, dr, IN, d0 ) )
        idx++;

      //assert( idx < 2 );

      Station S = var[idx];
      rail.push( S );

      // push to output
      stype[ord[i]] = S.type;
      loc[ord[i]] = S.x;

      if( S.type == C )
        leftmost = S.x < loc[leftmost] ? ord[i] : leftmost;

      if( S.type == D )
        rightmost = S.x > loc[rightmost] ? ord[i] : rightmost;
    }
  }
} solver;

void findLocation( int N, int first, int location[], int stype[] ) {
  solver.pass_param( N, first, location, stype );
  solver.solve();
}

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