# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
332417 |
2020-12-02T11:28:10 Z |
pggp |
Seats (IOI18_seats) |
C++14 |
|
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)
| ~~^~~~~~~~~~
# |
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 |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4065 ms |
39788 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
# |
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 |
- |
# |
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 |
- |