oj.uz

Submission #911430

# Submission time Handle Problem Language Result Execution time Memory
911430 2024-01-18T22:42:01 Z mircea_007 Rail (IOI14_rail) C++17
30 / 100
 46 ms 860 KB 
#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 );
      // if( it == Cs.begin() )
      //   printf( "UPS\n" );

      left = *(--Cs.upper_bound( A.x )); // vrem un C < A.x
      ret += A.x - left;
    }else
      left = A.x;

    if( B.type == C ){
      auto it = Ds.lower_bound( B.x );
      // if( it == Ds.end() )
      //   printf( "UPS\n" );

      right = *(Ds.lower_bound( B.x )); // 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] = 1;

    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] = 2;

    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();
}

Compilation message

rail.cpp: In member function 'int Railway::dist(Station, Station)':
rail.cpp:48:12: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   48 |       auto it = Cs.upper_bound( A.x );
      |            ^~
rail.cpp:58:12: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   58 |       auto it = Ds.lower_bound( B.x );
      |            ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 572 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 848 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -