제출 #1222610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222610		inesfi	자리 배치 (IOI18_seats)	C++20	17 / 100	4091 ms	150108 KiB

seats

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

#define ll long long

struct limite {
    int haut,bas,gauche,droite;
    
    void afficher(){
        cout<<"haut "<<haut<<" bas "<<bas<<" gauche "<<gauche<<" droite "<<droite<<endl;
    }
};

const int TAILLEMAXI=1000*1000+2,INFINI=1000*1000*1000;
vector<vector<int>> grille;
vector<int> lig,col;
int nblig,nbcol;
int rep;
bool ok[TAILLEMAXI];
vector<limite> limites;

void change(int deb,int fin){
    limite avant=limites[deb-1];
    for (int i=deb;i<=fin;i++){
        avant.haut=min(avant.haut,lig[i-1]);
        avant.bas=max(avant.bas,lig[i-1]);
        avant.gauche=min(avant.gauche,col[i-1]);
        avant.droite=max(avant.droite,col[i-1]);
        //avant.afficher();
        limites[i]=avant;
        if (ok[i]){
            rep--;
            ok[i]=false;
        }
        if ((avant.bas-avant.haut+1)*(avant.droite-avant.gauche+1)==i){
            rep++;
            //cout<<i<<endl;
            ok[i]=true;
        }
    }
}

void give_initial_chart(int nblignes, int nbcolonnes, vector<int> l, vector<int> c) {
    nblig=nblignes;
    nbcol=nbcolonnes;
    vector<vector<int>> tab(nblig,vector<int>(nbcol,0));
    for (int i=0;i<nblig*nbcolonnes;i++){
        tab[l[i]][c[i]]=i+1;
    }
    grille=tab;
    lig=l;
    col=c;
    limites.push_back({INFINI,-1,INFINI,-1});
    for (int i=1;i<=nblig*nbcol;i++){
        limites.push_back({0,0,0,0});
    }
    change(1,nblig*nbcol);
    //cout<<rep<<endl;
}

int swap_seats(int a, int b) {
    a++;
    b++;
    if (b<a){
        swap(a,b);
    }
    swap(lig[a-1],lig[b-1]);
    swap(col[a-1],col[b-1]);
    change(a,b);
    return rep;
}

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