Submission #294190

#	Time	Username	Problem	Language	Result	Execution time	Memory
294190		Saboon	Seats (IOI18_seats)	C++17	11 / 100	4073 ms	45176 KiB

seats

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, h, w;
vector<int> r, c;

int MxC[4*maxn], MxR[4*maxn], MnC[4*maxn], MnR[4*maxn];

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h = H, w = W, r = R, c = C;
	n = h*w;
	for (int i = 0; i < n; i++){
		MxC[i] = (i == 0 ? C[i] : max(MxC[i-1],C[i]));
		MnC[i] = (i == 0 ? C[i] : min(MnC[i-1],C[i]));
		MxR[i] = (i == 0 ? R[i] : max(MxR[i-1],R[i]));
		MnR[i] = (i == 0 ? R[i] : min(MnR[i-1],R[i]));
	}
}

int isGood(int r1, int r2, int c1, int c2){
	int Size = (r2-r1+1) * (c2-c1+1);
	if (Size == n)
		return 1;
	int idx = Size - 1;
	if (MxR[idx] > r2)
		r2 = MxR[idx];
	if (MnR[idx] < r1)
		r1 = MnR[idx];
	if (MxC[idx] > c2)
		c2 = MxC[idx];
	if (MnC[idx] < c1)
		c1 = MnC[idx];
	if ((r2-r1+1)*(c2-c1+1) != Size)
		return isGood(r1, r2, c1, c2);
		idx = Size;
	if (MxR[idx] > r2)
		r2 = MxR[idx];
	if (MnR[idx] < r1)
		r1 = MnR[idx];
	if (MxC[idx] > c2)
		c2 = MxC[idx];
	if (MnC[idx] < c1)
		c1 = MnC[idx];
	return 1 + isGood(r1,r2,c1,c2);
}

int swap_seats(int a, int b){
	if (a > b)
		swap(a,b);
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	for (int i = a; i < b; i++){
		MxC[i] = (i == 0 ? c[i] : max(MxC[i-1],c[i]));
		MnC[i] = (i == 0 ? c[i] : min(MnC[i-1],c[i]));
		MxR[i] = (i == 0 ? r[i] : max(MxR[i-1],r[i]));
		MnR[i] = (i == 0 ? r[i] : min(MnR[i-1],r[i]));
	}
	int r1 = r[0], r2 = r[0], c1 = c[0], c2 = c[0];
	return isGood(r1, r2, c1, c2);
}

Compilation message (stderr)

seats.cpp: In function 'int isGood(int, int, int, int)':
seats.cpp:33:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |  if ((r2-r1+1)*(c2-c1+1) != Size)
      |  ^~
seats.cpp:35:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   35 |   idx = Size;
      |   ^~~

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