Submission #808171

#	Time	Username	Problem	Language	Result	Execution time	Memory
808171		pravcoder	Seats (IOI18_seats)	C++14	11 / 100	4072 ms	24612 KiB

seats

#include "seats.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

vpi pos;
int h, w, n;

void give_initial_chart(int H, int W, vi R, vi C) {
	for (int i = 0; i < H*W; i++)
	{
		pos.push_back({ R[i], C[i] });
	}
	h = H, w = W, n = H * W;
}

int swap(int a, int b) {
	swap(pos[a], pos[b]);
	int k = 1;
	int minc, minr, maxc, maxr;
	minr = maxr = pos[0].first;
	minc = maxc = pos[0].second;
	for (int i = 1; i < n; i++)
	{
		minr = min(minr, pos[i].first);
		maxr = max(maxr, pos[i].first);
		minc = min(minc, pos[i].second);
		maxc = max(maxc, pos[i].second);
		int s = (maxc - minc + 1) * (maxr - minr + 1);
		if (s == i + 1) {
			k++;
		}
		else {
			i = min(i, s - 2);
		}
	}
	return k;
}

int swap_seats(int a, int b) {
	return swap(a, b);
}

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