Submission #829260

#	Time	Username	Problem	Language	Result	Execution time	Memory
829260		tranxuanbach	Seats (IOI18_seats)	C++17	11 / 100	4058 ms	44644 KiB

seats

#include "seats.h"

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

constexpr int inf = 1e9 + 7;

int n, m;
vector <vector <int>> a;

vector <pair <int, int>> pos;

void give_initial_chart(int _n, int _m, vector <int> _r, vector <int> _c){
	n = _n;
	m = _m;
	a.assign(n, vector <int>(m));
	pos.resize(n * m);
	for (int val = 0; val < n * m; val++){
		int x = _r[val], y = _c[val];
		a[x][y] = val;
		pos[val] = pair{x, y};
	}
}

int swap_seats(int val1, int val2){
	{
		auto [x1, y1] = pos[val1];
		auto [x2, y2] = pos[val2];
		swap(a[x1][y1], a[x2][y2]);
		swap(pos[val1], pos[val2]);
	}
	int ans = 0;
	int lx = inf, rx = -inf, ly = inf, ry = -inf;
	for (int val = 0; val < n * m; val++){
		auto &[x, y] = pos[val];
		lx = min(lx, x);
		rx = max(rx, x);
		ly = min(ly, y);
		ry = max(ry, y);
		if ((rx - lx + 1) * (ry - ly + 1) == val + 1){
			ans++;
		}
	}
	return ans;
}

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