Submission #287029

#	Time	Username	Problem	Language	Result	Execution time	Memory
287029		infinite_iq	Seats (IOI18_seats)	C++14	11 / 100	4021 ms	56744 KiB

seats

#include <bits/stdc++.h>
using namespace std ;
#define fi first 
#define se second 
typedef vector < int > vi ;
typedef pair < int , int > pi ;
#include "seats.h"
int n , m ;
vi a [10009] ;
pi id [10009] ;
int Mx ( int r1 , int r2 , int c1 , int c2 ) {
        if ( r1 > r2 ) swap ( r1 , r2 ) ;
        if ( c1 > c2 ) swap ( c1 , c2 ) ;
        if ( r1 < 0 || r2 >= n || c1 < 0 || c2 >= m ) return 1e9 ;
        int mx = 0 ;
        if ( r1 == r2 ) {
                for ( int i = c1 ; i <= c2 ; i ++ ) {
                        mx = max ( mx , a [r1][i] ) ;
                }
        }
        if ( c1 == c2 ) {
                for ( int i = r1 ; i <= r2 ; i ++ ) {
                        mx = max ( mx , a [i][c1] ) ;
                }
        }
        return mx ;
}
int solve () {
        int r1 , c1 , r2 , c2 , crnt = 0 , ans = 0 ;
        r1 = r2 = id [0].fi ;
        c1 = c2 = id [0].se ;
        while ( 1 ) {
        //      cout << r1 << " " << r2 << " " << c1 << " " << c2 << " " << crnt << endl ; 
                ans += ( crnt == ( r2 - r1 + 1 ) * ( c2 - c1 + 1 ) - 1 ) ;
                int val1 = Mx ( r1 - 1 , r1 - 1 , c1 , c2 ) ;
                int val2 = Mx ( r1 , r2 , c2 + 1 , c2 + 1 ) ;
                int val3 = Mx ( r2 + 1 , r2 + 1 , c1 , c2 ) ;
                int val4 = Mx ( r1 , r2 , c1 - 1 , c1 - 1 ) ;
        //      cout << val1 << " " << val2 << " " << val3 << " " << val4 << endl ;
        //      cout << "--------" << endl ; 
                int best = min ( min ( val1 , val2 ) , min ( val3 , val4 ) ) ;
                if ( best == 1e9 ) break ;
                if ( best == val1 ) {
                        r1 -- ;
                        crnt = max ( crnt , val1 ) ;
                        continue ;
                }
                if ( best == val2 ) {
                        c2 ++ ;
                        crnt = max ( crnt , val2 ) ;
                        continue ;
                }
                if ( best == val3 ) {
                        r2 ++ ;
                        crnt = max ( crnt , val3 ) ;
                        continue ;
                }
                if ( best == val4 ) {
                        c1 -- ;
                        crnt = max ( crnt , val4 ) ;
                        continue ;
                }
        }
        return ans ;
}
void give_initial_chart ( int H , int W , vi R, vi C) {
        n = H , m = W ;
        for ( int i = 0 ; i < n ; i ++ ) {
                a [i] .resize (m) ;
        }
        for ( int i = 0 ; i < n * m ; i ++ ) {
                a [R[i]][C[i]] = i ;
                id [i] = { R [i] , C [i] } ;
        }
/*      for ( int i = 0 ; i < n ; i ++ ) {
                for ( int j = 0 ; j < m ; j ++ ) {
                        cout << a [i][j] << " " ;
                }
                cout << endl ; 
        }*/
//      cout << solve () << endl ;
//      exit (0) ;
}
int swap_seats ( int x , int y ) {
        swap ( a [id[x].fi][id[x].se] , a [id[y].fi][id[y].se] ) ;
        swap ( id [x] , id [y] ) ;
/*      for ( int i = 0 ; i < n ; i ++ ) {
                for ( int j = 0 ; j < m ; j ++ ) {
                        cout << a [i][j] << " " ;
                }
                cout << endl ;
        }*/
        return solve () ;
}

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