제출 #403045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403045		jhnah917	자리 배치 (IOI18_seats)	C++14	5 / 100	4099 ms	35796 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
using namespace std;

constexpr int INF = 0x3f3f3f3f;

struct Node{
    int X1, X2, Y1, Y2;
    Node() : Node(INF, -INF, INF, -INF) {}
    Node(int x, int y) : Node(x, x, y, y) {}
    Node(int X1, int X2, int Y1, int Y2) : X1(X1), Y1(Y1), X2(X2), Y2(Y2) {}
    void set(int x, int y){ X1 = X2 = x; Y1 = Y2 = y; }
    bool in(const Node &t){
        return X1 <= t.X1 && t.X2 <= X2 && Y1 <= t.Y1 && t.Y2 <= Y2;
    }
    bool check(int sz){
        return (X2-X1+1) * (Y2-Y1+1) == sz;
    }
};
Node Merge(const Node &l, const Node &r){
    return {min(l.X1, r.X1), max(l.X2, r.X2), min(l.Y1, r.Y1), max(l.Y2, r.Y2)};
}

int N, M, K;
vector<int> X, Y;
vector<vector<int>> V, pX, sX, pY, sY;

void Update(int x, int y){
    pX[x][0] = V[x][0]; for(int j=1; j<M; j++) pX[x][j] = min(pX[x][j-1], V[x][j]);
    pY[0][y] = V[0][y]; for(int i=1; i<N; i++) pY[i][y] = min(pY[i-1][y], V[i][y]);
    sX[x][M-1] = V[x][M-1]; for(int j=M-2; j>=0; j--) sX[x][j] = min(sX[x][j+1], V[x][j]);
    sY[N-1][y] = V[N-1][y]; for(int i=N-2; i>=0; i--) sY[i][y] = min(sY[i+1][y], V[i][y]);
}

int Query(const Node &data){
    int ret = INF;
    for(int i=0; i<N; i++){
        if(data.Y1 > 0) ret = min(ret, pX[i][data.Y1-1]);
        if(data.Y2 < M-1) ret = min(ret, sX[i][data.Y2+1]);
    }
    for(int j=0; j<M; j++){
        if(data.X1 > 0) ret = min(ret, pY[data.X1-1][j]);
        if(data.X2 < N-1) ret = min(ret, sY[data.X2+1][j]);
    }
    return ret;
}

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<K; i++) V[X[i]][Y[i]] = i;
    pX = sX = pY = sY = V;
    for(int i=0; i<N; i++){
        for(int j=1; j<M; j++) pX[i][j] = min(pX[i][j-1], pX[i][j]);
        for(int j=M-2; j>=0; j--) sX[i][j] = min(sX[i][j+1], sX[i][j]);
    }
    for(int j=0; j<M; j++){
        for(int i=1; i<N; i++) pY[i][j] = min(pY[i-1][j], pY[i][j]);
        for(int i=N-2; i>=0; i--) sY[i][j] = min(sY[i+1][j], sY[i][j]);
    }
}

int swap_seats(int a, int b){
    swap(X[a], X[b]); swap(Y[a], Y[b]);
    swap(V[X[a]][Y[a]], V[X[b]][Y[b]]);
    Update(X[a], Y[a]); Update(X[b], Y[b]);

    int ret = 0;
    Node data(X[0], Y[0]);
    while(true){
        int t = Query(data);
        ret += data.check(t == INF ? K : t);
        if(t == INF) break;
        data = Merge(data, Node(X[t], Y[t]));
    }
    return ret;
}

#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

/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
 */

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In constructor 'Node::Node(int, int, int, int)':
seats.cpp:17:17: warning: 'Node::Y1' will be initialized after [-Wreorder]
   17 |     int X1, X2, Y1, Y2;
      |                 ^~
seats.cpp:17:13: warning:   'int Node::X2' [-Wreorder]
   17 |     int X1, X2, Y1, Y2;
      |             ^~
seats.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Node(int X1, int X2, int Y1, int Y2) : X1(X1), Y1(Y1), X2(X2), Y2(Y2) {}
      |     ^~~~

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