Submission #988070

# Submission time Handle Problem Language Result Execution time Memory
988070 2024-05-24T03:01:29 Z wood Seats (IOI18_seats) C++17
17 / 100
4000 ms 56512 KB
#include "seats.h"
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

namespace potato{
    int H,W; vi R,C;
}
vector<bool> res;
int ressum = 1;
vi rmin,rmax,cmin,cmax;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    potato::H = H, potato::W = W, potato::R = R, potato::C = C;
    int n = H*W;
    res.resize(n);
    rmin.resize(n); rmax.resize(n);  cmin.resize(n); cmax.resize(n);
    rmin[0] = R[0], rmax[0] = R[0], cmin[0] = C[0], cmax[0] = C[0];
    for (size_t i = 1; i < H*W; i++)
    {
        rmin[i] = min(rmin[i-1],R[i]); rmax[i] = max(rmax[i-1],R[i]);
        cmin[i] = min(cmin[i-1],C[i]); cmax[i] = max(cmax[i-1],C[i]);
        if(i+1==(rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1)){
            ressum++;
            res[i] = true;;
        }
    }
}

int swap_seats(int a, int b) {
    using namespace potato;
    swap(R[a],R[b]); swap(C[a],C[b]);
    if(a>b) swap(a,b);
    rmin[0] = R[0], rmax[0] = R[0], cmin[0] = C[0], cmax[0] = C[0];
    for(int i = max(a,1); i<b; i++){
        if(res[i]) ressum--;
        res[i] = false;
        rmin[i] = min(rmin[i-1],R[i]); rmax[i] = max(rmax[i-1],R[i]);
        cmin[i] = min(cmin[i-1],C[i]); cmax[i] = max(cmax[i-1],C[i]);
        if(i+1==(rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1)){
            ressum++;
            res[i] = true;
        }
    }
    return ressum;
}
// int main(int argc, char const *argv[])
// {
//     give_initial_chart(1,3,{0,0,0},{0,1,2});
//     cout<<swap_seats(1,2)<<'\n';
//     cout<<swap_seats(1,2)<<'\n';
//     return 0;
// }

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:39:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     for (size_t i = 1; i < H*W; i++)
      |                        ~~^~~~~
seats.cpp:43:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   43 |         if(i+1==(rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1)){
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 532 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 532 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 66 ms 860 KB Output is correct
14 Correct 67 ms 1020 KB Output is correct
15 Correct 68 ms 1044 KB Output is correct
16 Correct 76 ms 880 KB Output is correct
17 Correct 65 ms 1020 KB Output is correct
18 Correct 66 ms 860 KB Output is correct
19 Correct 68 ms 860 KB Output is correct
20 Correct 67 ms 1020 KB Output is correct
21 Correct 66 ms 1040 KB Output is correct
22 Correct 66 ms 856 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 55632 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 97 ms 872 KB Output is correct
2 Correct 223 ms 5200 KB Output is correct
3 Correct 403 ms 55632 KB Output is correct
4 Correct 421 ms 55460 KB Output is correct
5 Correct 421 ms 55600 KB Output is correct
6 Correct 401 ms 55592 KB Output is correct
7 Correct 402 ms 55592 KB Output is correct
8 Correct 394 ms 55632 KB Output is correct
9 Correct 401 ms 55632 KB Output is correct
10 Correct 405 ms 55724 KB Output is correct
11 Correct 408 ms 55636 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 2008 KB Output is correct
2 Correct 13 ms 2004 KB Output is correct
3 Correct 19 ms 1920 KB Output is correct
4 Correct 76 ms 2000 KB Output is correct
5 Correct 654 ms 2448 KB Output is correct
6 Execution timed out 4024 ms 56512 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 532 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 66 ms 860 KB Output is correct
14 Correct 67 ms 1020 KB Output is correct
15 Correct 68 ms 1044 KB Output is correct
16 Correct 76 ms 880 KB Output is correct
17 Correct 65 ms 1020 KB Output is correct
18 Correct 66 ms 860 KB Output is correct
19 Correct 68 ms 860 KB Output is correct
20 Correct 67 ms 1020 KB Output is correct
21 Correct 66 ms 1040 KB Output is correct
22 Correct 66 ms 856 KB Output is correct
23 Execution timed out 4046 ms 55632 KB Time limit exceeded
24 Halted 0 ms 0 KB -