oj.uz

Submission #969348

# Submission time Handle Problem Language Result Execution time Memory
969348 2024-04-25T03:03:45 Z steveonalex Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 14888 KB 
#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int INF = 1e9 + 69;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

#define Point pair<int, int>

vector<Point> dragon, verti_edge, hori_edge, vertices;
int xL, xR, yL, yR;
int cur_face;

void init(int n, int m, int sr, int sc, int k, char *S) {
    Point coord = {sr, sc};
    dragon.push_back(coord);
    for(int i = 0; i<k; ++i){
        if (S[i] == 'N') coord.first--;
        else if (S[i] == 'S') coord.first++;
        else if (S[i] == 'W') coord.second--;
        else coord.second++;

        dragon.push_back(coord);
    }

    remove_dup(dragon);

    for(pair<int, int> i: dragon){
        for(int d = 0; d < 4; ++d){
            if (d <= 1) hori_edge.push_back({i.first - (d == 0), i.second});
            else verti_edge.push_back({i.first, i.second - (d == 2)});
        }
    }

    remove_dup(hori_edge); remove_dup(verti_edge);

    for(pair<int, int> i: hori_edge) {
        vertices.push_back({i.first, i.second-1});
        vertices.push_back({i.first, i.second});
    }
    for(pair<int, int> i: verti_edge){
        vertices.push_back({i.first-1, i.second});
        vertices.push_back({i.first, i.second});
    }

    remove_dup(vertices);

    // cout << "Dragon: \n";
    // for(pair<int, int> i: dragon) cout << i.first << " " << i.second << "\n";
    // cout << "Horizontal Edge: \n";
    // for(pair<int, int> i: hori_edge) cout << i.first << " " << i.second << "\n";
    // cout << "Vertical Edge: \n";
    // for(pair<int, int> i: verti_edge) cout << i.first << " " << i.second << "\n";
    // cout << "Vertices: \n";
    // for(pair<int, int> i: vertices) cout << i.first << " " << i.second << "\n";

    cur_face = 2 + hori_edge.size() + verti_edge.size() - vertices.size() - dragon.size();
    xL = yL = INF;
    xR = yR = 0;
    for(pair<int, int> i: dragon){
        maximize(xR, i.first); maximize(yR, i.second);
        minimize(xL, i.first); minimize(yL, i.second);
    }
}

int colour(int ar, int ac, int br, int bc) {
    if (ar < xL && ac < yL && br > xR && bc > yR) return cur_face;
    int cnt = 0;
    int v_cnt = ((br - ar) + (bc - ac)) * 2, e_cnt = v_cnt;
    int block_cnt = 0;
    for(pair<int, int> i: dragon){
        if (ar <= i.first && i.first <= br && ac <= i.second && i.second <= bc)
            block_cnt++;
    }
    for(pair<int, int> i: vertices){
        if (ar <= i.first && i.first < br && ac <= i.second && i.second < bc)
            v_cnt++;
    }
    for(pair<int, int> i: hori_edge){
        if (ac <= i.second && i.second <= bc && ar <= i.first && i.first < br)
            e_cnt++;
    }
    for(pair<int, int> i: verti_edge){
        if (ar <= i.first && i.first <= br && ac <= i.second && i.second < bc)
            e_cnt++;
    }
    return 1 + e_cnt - v_cnt - block_cnt;
}


 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     freopen("input.inp", "r", stdin);

//     int n, m, k; cin >> n >> m;
//     int sr, sc; cin >> sr >> sc;
//     cin >> k;
//     string s; cin >> s;
//     init(n, m, sr, sc, k, (char*) s.c_str());

//     int q; cin >> q;
//     while(q--) {
//         int a, b, c, d; cin >> a >> b >> c >> d;
//         cout << colour(a, b, c, d) << "\n";
//     }
 
//     return 0;
// }

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:112:9: warning: unused variable 'cnt' [-Wunused-variable]
  112 |     int cnt = 0;
      |         ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 7 ms 592 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 15 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 3023 ms 8000 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 65 ms 13216 KB Output is correct
3 Correct 56 ms 13412 KB Output is correct
4 Correct 84 ms 12908 KB Output is correct
5 Correct 45 ms 9068 KB Output is correct
6 Correct 21 ms 4304 KB Output is correct
7 Correct 45 ms 4988 KB Output is correct
8 Correct 58 ms 14180 KB Output is correct
9 Correct 51 ms 9076 KB Output is correct
10 Correct 16 ms 2900 KB Output is correct
11 Correct 35 ms 8620 KB Output is correct
12 Correct 61 ms 14440 KB Output is correct
13 Correct 66 ms 13980 KB Output is correct
14 Correct 84 ms 14704 KB Output is correct
15 Correct 45 ms 9320 KB Output is correct
16 Correct 20 ms 4048 KB Output is correct
17 Correct 37 ms 4980 KB Output is correct
18 Correct 68 ms 14888 KB Output is correct
19 Correct 69 ms 14440 KB Output is correct
20 Correct 66 ms 13156 KB Output is correct
21 Correct 57 ms 13216 KB Output is correct
22 Correct 51 ms 8036 KB Output is correct
23 Correct 16 ms 2896 KB Output is correct
24 Correct 38 ms 8824 KB Output is correct
25 Correct 60 ms 14448 KB Output is correct
26 Correct 56 ms 14704 KB Output is correct
27 Correct 84 ms 14448 KB Output is correct
28 Correct 45 ms 8564 KB Output is correct
29 Correct 20 ms 4048 KB Output is correct
30 Correct 37 ms 4976 KB Output is correct
31 Correct 69 ms 14688 KB Output is correct
32 Correct 73 ms 14180 KB Output is correct
33 Correct 58 ms 14280 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 7 ms 592 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 15 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Execution timed out 3056 ms 8304 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 7 ms 592 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 15 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Execution timed out 3056 ms 8304 KB Time limit exceeded
19 Halted 0 ms 0 KB -