oj.uz

Submission #332417

# Submission time Handle Problem Language Result Execution time Memory
332417 2020-12-02T11:28:10 Z pggp Seats (IOI18_seats) C++14
17 / 100
 4000 ms 55916 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 4 ms 372 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 4 ms 372 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 132 ms 876 KB Output is correct
14 Correct 131 ms 748 KB Output is correct
15 Correct 129 ms 748 KB Output is correct
16 Correct 125 ms 804 KB Output is correct
17 Correct 132 ms 748 KB Output is correct
18 Correct 128 ms 748 KB Output is correct
19 Correct 131 ms 876 KB Output is correct
20 Correct 128 ms 1004 KB Output is correct
21 Correct 126 ms 748 KB Output is correct
22 Correct 124 ms 748 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 39788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 812 KB Output is correct
2 Correct 485 ms 3820 KB Output is correct
3 Correct 640 ms 39788 KB Output is correct
4 Correct 670 ms 55916 KB Output is correct
5 Correct 641 ms 55916 KB Output is correct
6 Correct 655 ms 55660 KB Output is correct
7 Correct 675 ms 55660 KB Output is correct
8 Correct 665 ms 55660 KB Output is correct
9 Correct 673 ms 55660 KB Output is correct
10 Correct 665 ms 55660 KB Output is correct
11 Correct 657 ms 55660 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1384 KB Output is correct
2 Correct 25 ms 1512 KB Output is correct
3 Correct 32 ms 1384 KB Output is correct
4 Correct 143 ms 1384 KB Output is correct
5 Correct 1258 ms 1776 KB Output is correct
6 Execution timed out 4088 ms 39916 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 4 ms 372 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 132 ms 876 KB Output is correct
14 Correct 131 ms 748 KB Output is correct
15 Correct 129 ms 748 KB Output is correct
16 Correct 125 ms 804 KB Output is correct
17 Correct 132 ms 748 KB Output is correct
18 Correct 128 ms 748 KB Output is correct
19 Correct 131 ms 876 KB Output is correct
20 Correct 128 ms 1004 KB Output is correct
21 Correct 126 ms 748 KB Output is correct
22 Correct 124 ms 748 KB Output is correct
23 Execution timed out 4065 ms 39788 KB Time limit exceeded
24 Halted 0 ms 0 KB -