Submission #395341

#	Time	Username	Problem	Language	Result	Execution time	Memory
395341		Mounir	Seats (IOI18_seats)	C++14	11 / 100	4072 ms	40384 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;

struct Extremums {
	int xMin, xMax, yMin, yMax;
};

struct Point {
	int x, y;
};

int nLigs, nCols, nVals;
const int MAX_VALS = 1e6 + 1;
Extremums vals[MAX_VALS];
bool estOk[MAX_VALS];
Point points[MAX_VALS];

int sum = 0;

void construire(int iVal){
	if (iVal == 0){
		vals[0] = {points[0].x, points[0].x, points[0].y, points[0].y};
		return;
	}

	vals[iVal] = vals[iVal - 1];
	chmin(vals[iVal].xMin, points[iVal].x);
	chmax(vals[iVal].xMax, points[iVal].x);
	chmin(vals[iVal].yMin, points[iVal].y);
	chmax(vals[iVal].yMax, points[iVal].y);
	int aire = (vals[iVal].xMax - vals[iVal].xMin + 1) * (vals[iVal].yMax - vals[iVal].yMin + 1);
	sum -= estOk[iVal];
	if (aire == iVal + 1)
		estOk[iVal] = true;
	else
		estOk[iVal] = false;
	sum += estOk[iVal];
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	nLigs = H;
	nCols = W;
	nVals = nLigs * nCols;
	for (int iVal = 0; iVal < nVals; ++iVal)
		points[iVal] = {R[iVal], C[iVal]};

	vals[0] = {points[0].x, points[0].x, points[0].y, points[0].y};
	estOk[0] = true; sum++;
	for (int iVal = 1; iVal < nVals; ++iVal)
		construire(iVal);

}

int swap_seats(int a, int b) {
	swap(points[a], points[b]);
	for (int iVal = 0; iVal < nVals; ++iVal)
		construire(iVal);
	return sum;
}

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