제출 #284104

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

seats

#include <bits/stdc++.h>
using namespace std;

const int c=1000002;
int n, m, sor[c], oszlop[c], db, kiss[c], nagys[c], kiso[c], nagyo[c];
bool jo[c];



int swap_seats(int a, int b) {
    swap(sor[a], sor[b]), swap(oszlop[a], oszlop[b]);
    for (int i=a; i<b; i++) {
        if (i==0) kiss[0]=sor[0], nagys[a]=sor[0], kiso[a]=oszlop[0], nagyo[a]=oszlop[0];
        else kiss[i]=min(kiss[i-1], sor[i]), nagys[i]=max(nagys[i-1], sor[i]), kiso[i]=min(kiso[i-1], oszlop[i]), nagyo[i]=max(nagyo[i-1], oszlop[i]);
        db-=jo[i];
        if ((nagys[i]-kiss[i]+1)*(nagyo[i]-kiso[i]+1)==i+1) jo[i]=1, db++;
    }
    return db;
}
void give_initial_chart(int a, int b, vector<int> c, vector<int> d) {
    n=a, m=b;
    for (int i=0; i<n*m; i++) sor[i]=c[i], oszlop[i]=d[i];
    int db=0, ks=n, ns=0, ko=m, no=0;
    for (int i=0; i<n*m; i++) {
        ks=min(ks, sor[i]), ko=min(ko, oszlop[i]);
        ns=max(ns, sor[i]), no=max(no, oszlop[i]);
        kiss[i]=ks, nagys[i]=ns, kiso[i]=ko, nagyo[i]=no;
        if ((ns-ks+1)*(no-ko+1)==i+1) jo[i]=1, db++;
    }
}

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