Submission #107527

#	Time	Username	Problem	Language	Result	Execution time	Memory
107527		kyunamk	Seats (IOI18_seats)	C++14	11 / 100	4101 ms	32120 KiB

seats

#include "seats.h"
#include <utility>

#include <iostream>

using namespace std;
std::vector<int> r;
std::vector<int> c;
std::vector< pair<int,int> > pos;

int K;
// int debug = true; //false;
int debug = false;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = R;
  c = C;

  K = R.size();
  pos.resize(K);
  for ( int i = 0  ; i < K ; i++) {
    // if( debug ) cout << R[i] << C[i] << endl;
    pos[i]=make_pair(R[i],C[i]);
  }
  // debug = true;
}

int r1,r2,c1,c2;
static inline int add_rect( int r, int c)
{
  int changed = 0;
  if ( r >= r1 && r <= r2 && c >= c1 && c <= c2) changed = 0;
  else {
    if ( r < r1 ) r1 = r;
    else if( r > r2 ) r2 = r;

    if ( c < c1 ) c1 = c;
    else if( c > c2 ) c2 = c;
    changed = 1;
  }

  return changed ;
}
int swap_seats(int a, int b) {
  if( debug ) cout << "Swap : " << a << b << endl;
  pair<int,int> t = pos[b];
  pos[b]=pos[a];
  pos[a]=t;
  r1=r2=pos[0].first;
  c1=c2=pos[0].second;
  int cnt = 0;
  if( debug ) cout << 0 << r1 << r2 << c1 << c2 << endl;
  for( int i =0 ; i < K ; i++ ) {
    int changed = add_rect( pos[i].first , pos[i].second ) ;
    if( debug ) { cout << i << changed << r1 << r2 << c1 << c2 << endl; }
    if ( (r2-r1+1)*(c2-c1+1) == i+1 ) {
      if( debug ) cout << "BRect " << i+1 << endl;
      cnt++;
    } else {
      // int j , k ;
      // k = (r2-r1+1)*(c2-c1+1);
      // for( j =i ; j < k-1 ; j++ ) {
      //   if ( add_rect( pos[i].first , pos[i].second ) )
      //     k = (r2-r1+1)*(c2-c1+1);
      // }
      // i=j;
    }
  }
  return cnt;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30