제출 #138847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138847		Arturgo	자리 배치 (IOI18_seats)	C++14	37 / 100	4094 ms	148236 KiB

seats

#include "seats.h"
#include <algorithm>
#include <iostream>
using namespace std;

const int NB_FEUILLES = (1 << 20);
const int INFINI = NB_FEUILLES;

pair<int, int> modifs[2 * NB_FEUILLES];
int nombres[2 * NB_FEUILLES][5];

int nbLigs, nbCols;

vector<pair<int, int>> coords;
vector<vector<int>> sieges;

inline void update(int noeud) {
	if(modifs[noeud].second != 0)
		return;

	for(int i = 0;i < 5;i++)
		nombres[noeud][i] = 0;

	if(noeud >= NB_FEUILLES) {
		if(modifs[noeud].first <= 4) {
			nombres[noeud][modifs[noeud].first]++;
		}
		return;
	}

	for(int i = modifs[noeud].first;i < 5;i++) {
		if(modifs[2 * noeud].second == 0)
			nombres[noeud][i] += nombres[2 * noeud][i - modifs[noeud].first];
		if(modifs[2 * noeud + 1].second == 0)
			nombres[noeud][i] += nombres[2 * noeud + 1][i - modifs[noeud].first];
	}
}

inline int nbRectangles() {
	if(modifs[1].second != 0)
		return 0;
	return nbLigs * nbCols + nombres[1][4] - NB_FEUILLES;
}

void ajoute(int deb, int fin, pair<int, int> modif, int n = 1, int d = 0, int f = NB_FEUILLES) {
	if(deb >= f || d >= fin)
		return;
	if(deb <= d && f <= fin) {
		modifs[n].first += modif.first;
		modifs[n].second += modif.second;
		update(n);
		return;
	}

	int m = (d + f) / 2;
	ajoute(deb, fin, modif, 2 * n, d, m);
	ajoute(deb, fin, modif, 2 * n + 1, m, f);
	update(n);
}

inline void update(int lig, int col, int sens) {
	if(lig < 0 || col < 0 || lig > nbLigs || col > nbCols)
		return;

	int vals[4] = {
		sieges[lig][col], 
		sieges[lig + 1][col], 
		sieges[lig + 1][col + 1],
		sieges[lig][col + 1]
	};

	sort(vals, vals + 4);

	ajoute(vals[0], vals[1], {sens, 0});
	ajoute(vals[2], vals[3], {0, sens});
}

void give_initial_chart(int _nbLigs, int _nbCols, vector<int> ligs, vector<int> cols) {
	nbLigs = _nbLigs;
	nbCols = _nbCols;
	sieges = vector<vector<int>>(nbLigs + 2, vector<int>(nbCols + 2, INFINI));
 	for(int iEleve = 0;iEleve < nbLigs * nbCols;iEleve++) {
 		coords.push_back({ligs[iEleve] + 1, cols[iEleve] + 1});
 		sieges[ligs[iEleve] + 1][cols[iEleve] + 1] = iEleve;
 	}

 	for(int iSommet = 2 * NB_FEUILLES - 1;iSommet >= 1;iSommet--) {
 		update(iSommet);
 	}

 	for(int iLig = 0;iLig < nbLigs + 2;iLig++) {
 		for(int iCol = 0;iCol < nbCols + 2;iCol++) {
 			update(iLig, iCol, 1);
 		}
 	}
}

inline void ajoutePos(int lig, int col, vector<pair<int, int>>& pos) {
	pos.push_back({lig - 1, col - 1});
	pos.push_back({lig - 1, col});
	pos.push_back({lig, col - 1});
	pos.push_back({lig, col});
}

int swap_seats(int a, int b) {
	vector<pair<int, int>> positions;
	ajoutePos(coords[a].first, coords[a].second, positions);
	ajoutePos(coords[b].first, coords[b].second, positions);

	sort(positions.begin(), positions.end());

	vector<pair<int, int>> reprs;
	pair<int, int> der = {-1, -1};
	for(pair<int, int> pos : positions) {
		if(pos != der) {
			der = pos;
			reprs.push_back(der);
		}
	}

	for(pair<int, int> pos : reprs) {
		update(pos.first, pos.second, -1);
	}

	swap(sieges[coords[a].first][coords[a].second], sieges[coords[b].first][coords[b].second]);
	swap(coords[a], coords[b]);

	for(pair<int, int> pos : reprs) {
		update(pos.first, pos.second, 1);
	}

  	return nbRectangles();
}

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