oj.uz

Submission #837934

# Submission time Handle Problem Language Result Execution time Memory
837934 2023-08-25T20:45:01 Z FulopMate Seats (IOI18_seats) C++17
17 / 100
 4000 ms 55624 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<pair<int,int>> v;
vector<int> a, b, c, d;
vector<bool> lehet;
int ans;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H*W;
    v.resize(n);
    a.resize(n); b.resize(n);
    c.resize(n); d.resize(n);
    lehet.resize(n);
    for(int i = 0; i < n; i++){
        v[i] = {R[i], C[i]};
    }

    int ca = v[0].first, cb = v[0].first, cc = v[0].second, cd = v[0].second;
    a[0] = ca, b[0] = cb, c[0] = cc, d[0] = cd;
    lehet[0] = 1;
    ans = 1;
    for(int i = 1; i < n; i++){
        ca = min(ca, v[i].first);
        cb = max(cb, v[i].first);
        cc = min(cc, v[i].second);
        cd = max(cd, v[i].second);
        if(i+1 == (cb-ca+1)*(cd-cc+1)){
            lehet[i] = true;
            ans++;
        }
        a[i] = ca, b[i] = cb, c[i] = cc, d[i] = cd;
    }
}

int swap_seats(int x, int y) {
    swap(v[x], v[y]);
    if(x > y)swap(x, y);
    int ca, cb, cc, cd;
    if(x == 0){
        ca = v[0].first; cb = v[0].first;
        cc = v[0].second; cd = v[0].second;
    } else {
        ca = a[x-1]; cb = b[x-1];
        cc = c[x-1]; cd = d[x-1];
    }
    for(int i = x; i <= y; i++){
        ca = min(ca, v[i].first);
        cb = max(cb, v[i].first);
        cc = min(cc, v[i].second);
        cd = max(cd, v[i].second);
        if(i+1 == (cb-ca+1)*(cd-cc+1)){
            if(!lehet[i]){
                lehet[i] = true;
                ans++;
            }
        } else {
            if(lehet[i]){
                lehet[i] = false;
                ans--;
            }
        }
        a[i] = ca, b[i] = cb, c[i] = cc, d[i] = cd;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 3 ms 440 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 3 ms 440 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 59 ms 852 KB Output is correct
14 Correct 57 ms 972 KB Output is correct
15 Correct 53 ms 904 KB Output is correct
16 Correct 59 ms 852 KB Output is correct
17 Correct 53 ms 888 KB Output is correct
18 Correct 55 ms 972 KB Output is correct
19 Correct 53 ms 900 KB Output is correct
20 Correct 55 ms 908 KB Output is correct
21 Correct 56 ms 896 KB Output is correct
22 Correct 55 ms 888 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 724 KB Output is correct
2 Correct 97 ms 4428 KB Output is correct
3 Correct 266 ms 40128 KB Output is correct
4 Correct 260 ms 55500 KB Output is correct
5 Correct 263 ms 55624 KB Output is correct
6 Correct 255 ms 55500 KB Output is correct
7 Correct 255 ms 55500 KB Output is correct
8 Correct 256 ms 55500 KB Output is correct
9 Correct 268 ms 55504 KB Output is correct
10 Correct 271 ms 55500 KB Output is correct
11 Correct 259 ms 55468 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1360 KB Output is correct
2 Correct 14 ms 1360 KB Output is correct
3 Correct 19 ms 1872 KB Output is correct
4 Correct 65 ms 2016 KB Output is correct
5 Correct 511 ms 2248 KB Output is correct
6 Execution timed out 4027 ms 39880 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 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 3 ms 440 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 59 ms 852 KB Output is correct
14 Correct 57 ms 972 KB Output is correct
15 Correct 53 ms 904 KB Output is correct
16 Correct 59 ms 852 KB Output is correct
17 Correct 53 ms 888 KB Output is correct
18 Correct 55 ms 972 KB Output is correct
19 Correct 53 ms 900 KB Output is correct
20 Correct 55 ms 908 KB Output is correct
21 Correct 56 ms 896 KB Output is correct
22 Correct 55 ms 888 KB Output is correct
23 Execution timed out 4070 ms 39500 KB Time limit exceeded
24 Halted 0 ms 0 KB -