제출 #287803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287803		Ozy	자리 배치 (IOI18_seats)	C++17	0 / 100	4102 ms	23968 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " = " << a << endl

struct x{
    int MAXf;
    int MINf;

    int MAXc;
    int MINc;

    int hizq;
    int hder;
};

struct y{
    int fil;
    int col;
};

int cont,n,p,res;
x uso,maximos;
x ST[2100000];
y id[1000002];

void h(int pos){

    ST[pos].hizq = cont++;
    ST[pos].hder = cont++;

}

x crea(int ini, int fin, int num, x des, int pos) {
    x a,b;
    int mitad;

    if (ini == fin && ini == num) {
        ST[pos].MAXf = des.MAXf;
        ST[pos].MAXc = des.MAXc;
        ST[pos].MINf = des.MINf;
        ST[pos].MINc = des.MINc;

        return ST[pos];
    }
    else if (ini <= num && fin >= num) {

        mitad = (ini+fin) / 2;

        if (ST[pos].hizq = 0) h(pos);

        a = crea(ini, mitad, num, des, ST[pos].hizq);
        b = crea(mitad + 1, fin, num, des, ST[pos].hder);

        ST[pos].MAXf = max(a.MAXf, b.MAXf);
        ST[pos].MINf = min(a.MINf, b.MINf);
        ST[pos].MAXc = max(a.MAXc, b.MAXc);
        ST[pos].MINc = min(a.MINc, b.MINc);

        return ST[pos];

    }
    return {0, 1000002, 0, 1000002, 0, 0};

}

x query(int nodo, int ini, int fin, int r) {
    int mitad;
    x a,b;

    if (fin <= r) {

        return ST[nodo];

    }
    else if (ini <= r) {

        mitad = (ini+fin) / 2;
        a = query(ST[nodo].hizq,ini,mitad, r);
        b = query(ST[nodo].hder,mitad+1,fin, r);

        a.MAXf = max(a.MAXf, b.MAXf);
        a.MINf = min(a.MINf, b.MINf);
        a.MAXc = max(a.MAXc, b.MAXc);
        a.MINc = min(a.MINc, b.MINc);

        return a;

    }
    return {0, 1000002,0, 1000002,0,0};
}

bool checa(x act, int val) {
    int l1,l2;

    l1 = act.MAXf - act.MINf + 1;
    l2 = act.MAXc - act.MINc + 1;

    l1 *= l2;

    return (l1 == (val+1));

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {

    n = H*W;

    cont = 2;
    rep(i, 0, n-1) {

        id[i] = {R[i], C[i]};

        uso = {R[i], R[i], C[i], C[i], 0, 0};
        uso = crea(0, n-1, i, uso, 1);
    }

}

int swap_seats(int a, int b) {

    uso = {id[a].fil, id[a].fil, id[a].col, id[a].col,0,0};
    crea(0, n-1, b, uso, 1);

    uso = {id[b].fil, id[b].fil, id[b].col, id[b].col,0,0};
    crea(0, n-1, a, uso, 1);

    swap(id[a], id[b]);


    p = 0;
    maximos = {id[p].fil, id[p].fil, id[p].col, id[p].col, 0 ,0};
    res = 0;

    while (p < n) {

        maximos = query(1, 0, n-1, p);

        if (checa(maximos, p)) {
            res++;
            p++;
        }
        else p = (maximos.MAXf - maximos.MINf + 1) * (maximos.MAXc - maximos.MINc + 1) - 1;

    }

    return res;

}

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

seats.cpp: In function 'x crea(int, int, int, x, int)':
seats.cpp:51:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   51 |         if (ST[pos].hizq = 0) h(pos);
      |             ~~~~~~~~~~~~~^~~

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