oj.uz

Submission #1019218

# Submission time Handle Problem Language Result Execution time Memory
1019218 2024-07-10T15:46:22 Z Ausp3x Vision Program (IOI19_vision) C++17
58 / 100
 5 ms 1240 KB 
// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "vision.h"
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

#ifdef DEBUG
vector<bool> arr;
void add_not(int N) {
    arr.pb(~arr[N]);

    return;
}

void add_and(vector<int> Ns) {
    bool res = 1;
    for (int N : Ns)
        res &= arr[N];
    arr.pb(res);

    return;
}

void add_or(vector<int> Ns) {
    bool res = 0;
    for (int N : Ns)
        res |= arr[N];
    arr.pb(res);

    return;
}

void add_xor(vector<int> Ns) {
    bool res = 0;
    for (int N : Ns)
        res ^= arr[N];
    arr.pb(res);

    return;
}
#endif

void construct_network(int H, int W, int K) {
    // H rows
    vector<int> row_queries(W);
    for (int j = 1; j < W; j++)
        row_queries[j] = row_queries[j - 1] + 1;
    add_or(row_queries);
    
    for (int i = 1; i < H; i++) {
        for (int j = 0; j < W; j++)
            row_queries[j] += W;
        
        add_or(row_queries);
    }

    // W columns
    vector<int> col_queries(H);
    for (int i = 1; i < H; i++)
        col_queries[i] = col_queries[i - 1] + W;
    add_or(col_queries);

    for (int j = 1; j < W; j++) {
        for (int i = 0; i < H; i++)
            col_queries[i]++;

        add_or(col_queries);
    }

    vector<int> one_col_chk;
    for (int j = H * W + H; j < H * W + H + W; j++)
        one_col_chk.push_back(j);
    add_xor(one_col_chk);

    // cout << arr[H * W + H + W] << endl;

    vector<int> one_row_chk;
    for (int i = H * W; i < H * W + H; i++)
        one_row_chk.push_back(i);
    add_xor(one_row_chk);

    // cout << arr[H * W + H + W + 1] << endl;

    int cnt = H * W + H + W + 2;
    if (K < H)
        for (int i = H * W; i + K < H * W + H; i++) {
            add_and({i, i + K, H * W + H + W});
            cnt++;
        }
    if (K < W)
        for (int j = H * W + H; j + K < H * W + H + W; j++) {
            add_and({j, j + K, H * W + H + W + 1});
            cnt++;
        }
    for (int di = 1; di < K; di++) {
        int dj = K - di;
        for (int i = H * W; i + di < H * W + H; i++)
            for (int j = H * W + H; j + dj < H * W + H + W; j++) {
                add_and({i, i + di, j, j + dj});
                cnt++;
            }
    }

    vector<int> last_query;
    for (int i = H * W + H + W + 2; i < cnt; i++)
        last_query.push_back(i);
    add_or(last_query);

    return;
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        int H, W, K;
        cin >> H >> W >> K;
        arr.clear();
        arr.resize(H * W);
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        arr[r1 * W + c1] = 1;
        arr[r2 * W + c2] = 1;

        construct_network(H, W, K);

        cout << arr.back() << endl;
    }

    return 0;
}
#endif

Compilation message

vision.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
vision.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
vision.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
vision.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
In file included from vision.cpp:7:
vision.h:8:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    8 | void construct_network(int H, int W, int K);
      |                                           ^
vision.h:8:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:8:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   10 | int add_and(std::vector<int> Ns);
      |                                ^
vision.h:10:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:10:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   12 | int add_or(std::vector<int> Ns);
      |                               ^
vision.h:12:31: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:12:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   14 | int add_xor(std::vector<int> Ns);
      |                                ^
vision.h:14:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:14:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   16 | int add_not(int N);
      |                  ^
vision.h:16:18: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.h:16:18: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
vision.cpp:56:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   56 | void construct_network(int H, int W, int K) {
      |                                           ^
vision.cpp:56:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
vision.cpp:56:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
vision.cpp:56:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 4 ms 984 KB Output is correct
35 Correct 3 ms 728 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 428 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 4 ms 984 KB Output is correct
35 Correct 3 ms 728 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 428 KB Output is correct
38 Incorrect 1 ms 1116 KB WA in grader: Too many instructions
39 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 428 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 1240 KB WA in grader: Too many instructions
5 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1112 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 5 ms 1204 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 4 ms 984 KB Output is correct
35 Correct 3 ms 728 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 428 KB Output is correct
38 Incorrect 1 ms 1116 KB WA in grader: Too many instructions
39 Halted 0 ms 0 KB -