# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
831456 |
2023-08-20T09:19:10 Z |
tolbi |
Seats (IOI18_seats) |
C++17 |
|
4000 ms |
33200 KB |
#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
struct BIT{
vector<int> arr;
BIT(int n){
arr.resize(n,0);
}
void update(int x, int val){
arr[x]=val;
}
int query(int l, int r){
int rval = 23232323;
for (int i = l; i <= r; i++){
rval=min(rval,arr[i]);
}
return rval;
}
};
vector<int> R,C;
vector<BIT> horizontal;
vector<BIT> vertical;
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
R=_R,C=_C;
horizontal.resize(W,H);
vertical.resize(H,W);
for (int i = 0; i < R.size(); ++i)
{
vertical[R[i]].update(C[i],i);
horizontal[C[i]].update(R[i],i);
}
}
int swap_seats(int a, int b) {
swap(R[a],R[b]);
swap(C[a],C[b]);
vertical[R[a]].update(C[a],a);
vertical[R[b]].update(C[b],b);
horizontal[C[a]].update(R[a],a);
horizontal[C[b]].update(R[b],b);
int n = R.size();
int crmax = 0;
int ans = 1;
int xl=R[0],xr=R[0];
int yl=C[0],yr=C[0];
while (crmax<R.size()-1){
int sec1=n, sec2=n, sec3=n, sec4=n;
if (yl>0){
sec1=horizontal[yl-1].query(xl,xr);
}
if (yr<horizontal.size()-1){
sec2=horizontal[yr+1].query(xl,xr);
}
if (xl>0){
sec3=vertical[xl-1].query(yl,yr);
}
if (xr<vertical.size()-1){
sec4=vertical[xr+1].query(yl,yr);
}
int minel = n;
minel=min(minel,sec1);
minel=min(minel,sec2);
minel=min(minel,sec3);
minel=min(minel,sec4);
xr=max(xr,R[minel]);
xl=min(xl,R[minel]);
yr=max(yr,C[minel]);
yl=min(yl,C[minel]);
crmax=max(crmax,minel);
if ((xr-xl+1)*(yr-yl+1)==crmax+1) ans++;
}
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 = 0; i < R.size(); ++i)
| ~~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while (crmax<R.size()-1){
| ~~~~~^~~~~~~~~~~
seats.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (yr<horizontal.size()-1){
| ~~^~~~~~~~~~~~~~~~~~~~
seats.cpp:58:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (xr<vertical.size()-1){
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4038 ms |
33200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
111 ms |
820 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
2004 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |