Submission #402847

#	Time	Username	Problem	Language	Result	Execution time	Memory
402847		jhnah917	Seats (IOI18_seats)	C++14	11 / 100	4046 ms	40756 KiB

seats

/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#ifndef LOCAL
#include "seats.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
constexpr int INF = 0x3f3f3f3f;

int N, M, K;
vector<int> X, Y;
vector<vector<int>> V;

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C){
    N = H; M = W; K = N * M;
    swap(X, _R); swap(Y, _C);
    V = vector<vector<int>>(N, vector<int>(M));
    for(int i=0; i<N*M; i++) V[X[i]][Y[i]] = i;
}

// 11 pts
int Subtask2(int u, int v){
    int ret = 0, X1 = INF, X2 = -INF, Y1 = INF, Y2 = -INF;
    swap(V[X[u]][Y[u]], V[X[v]][Y[v]]);
    swap(X[u], X[v]); swap(Y[u], Y[v]);
    for(int i=0; i<K; i++){
        X1 = min(X1, X[i]); X2 = max(X2, X[i]);
        Y1 = min(Y1, Y[i]); Y2 = max(Y2, Y[i]);
        if((X2-X1+1)*(Y2-Y1+1) == i+1) ret++;
    }
    return ret;
}

int swap_seats(int a, int b){
    if(N*M <= 10000) return Subtask2(a, b);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int H, W, Q;
    cin >> H >> W >> Q;
    vector<int> R(H*W), C(H*W);
    for(int i=0; i<H*W; i++) cin >> R[i] >> C[i];
    vector<int> A(Q), B(Q);
    for(int i=0; i<Q; i++) cin >> A[i] >> B[i];
    give_initial_chart(H, W, R, C);
    for(int i=0; i<Q; i++){
        cout << swap_seats(A[i], B[i]) << "\n";
    }
    return 0;
}
#endif

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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