Submission #332417

#	Time	Username	Problem	Language	Result	Execution time	Memory
332417		pggp	Seats (IOI18_seats)	C++14	17 / 100	4088 ms	55916 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

using namespace std;

int H, W;
int total;
vector < int > R, C;
int ans;
vector < int > min_x, min_y, max_x, max_y;
vector < bool > ok;

void give_initial_chart(int H_1, int W_1, vector < int > R_1, vector < int > C_1){
	H = H_1;
	W = W_1;
	R = R_1;
	C = C_1;
	total = H * W;
	min_x.resize(total);
	max_x.resize(total);
	max_y.resize(total);
	min_y.resize(total);
	min_y[0] = R[0];
	max_y[0] = R[0];
	min_x[0] = C[0];
	max_x[0] = C[0];
	ok.resize(total);
	for (int i = 1; i < R.size(); ++i)
	{

		//cout << "i: " << i << endl;
		//cout << "max_x = " << max_x << " max_y = " << max_y << " ";  
		//cout << "min_x = " << min_x << " min_y = " << min_y << " ";  
		//cout << endl;
		if((max_x[i - 1] - min_x[i - 1] + 1) * (max_y[i - 1] - min_y[i - 1] + 1) == i){
			ans++;
			ok[i - 1] = true;
			//cout << "i: " << i << endl;
		}

		max_x[i] = max(max_x[i - 1], C[i]);
		max_y[i] = max(max_y[i - 1], R[i]);
		min_x[i] = min(min_x[i - 1], C[i]);
		min_y[i] = min(min_y[i - 1], R[i]);
	}
	ans += 1;
	ok[total - 1] = true;
}

int swap_seats(int a, int b){
	if(a > b){
		return swap_seats(b, a);
	}
	int r_a, c_a;
	r_a = R[a];
	c_a = C[a];
	R[a] = R[b];
	C[a] = C[b];
	R[b] = r_a;
	C[b] = c_a;
	for (int i = a; i <= b; ++i)
	{
		if(i > 0){
			max_x[i] = max(max_x[i - 1], C[i]);
			max_y[i] = max(max_y[i - 1], R[i]);
			min_x[i] = min(min_x[i - 1], C[i]);
			min_y[i] = min(min_y[i - 1], R[i]);
		}
		else{		
			min_y[0] = R[0];
			max_y[0] = R[0];
			min_x[0] = C[0];
			max_x[0] = C[0];
		}
		
	}


	for (int i = a; i <= b; ++i)
	{
		if((max_x[i] - min_x[i] + 1) * (max_y[i] - min_y[i] + 1) == i + 1){
			if(!ok[i]){
				ans++;
			}
			ok[i] = true;
		}
		else{
			if(ok[i]){
				ans--;
				//cout << "i: " << i << endl;
			}
			ok[i] = false;
		}

	}
	return ans;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 1; i < R.size(); ++i)
      |                  ~~^~~~~~~~~~

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