oj.uz

답안 #256572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256572 2020-08-02T21:08:39 Z fivefourthreeone Vision Program (IOI19_vision) C++17
12 / 100
 19 ms 2296 KB 
#include <bits/stdc++.h>
#include "vision.h"
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gpu_hash_map<int, int> mp;*/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = -1e6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
int h, w, k;
int cnt, nxt;
/*int arr[1000001];
void add_not(int a){
    arr[nxt++] = arr[a]^1;
}
void add_or(vector<int> a){
    int nw = 0;
    for(int p: a) {
        nw|=arr[p];
    }
    arr[nxt++] = nw;
}
void add_and(vector<int> a){
    int nw = 1;
    for(int p: a) {
        nw&=arr[p];
    }
    arr[nxt++] = nw;
}
void add_xor(vector<int> a){
    int nw = 0;
    for(int p: a) {
        nw^=arr[p];
    }
    arr[nxt++] = nw;
}*/
int _add_not(int a) {add_not(a);return cnt++;}
int _add_or(vector<int> a) {add_or(a);return cnt++;}
int _add_and(vector<int> a) {add_and(a);return cnt++;}
int _add_xor(vector<int> a) {add_xor(a);return cnt++;}
int val(int x, int y) {
    return x*w + y;
}
int solve(int d) {
    //query for all up diagonals
    vector<int> qq;
    vector<int> up;
    vector<int> down;
    owo(i, 0, h) {
        qq.clear();
        owo(j, 0, min(i+1, w)) {
            qq.senpai(val(i-j, j));
        }
        up.senpai(_add_or(qq));
    }
    owo(i, 1, w) {
        qq.clear();
        owo(j, 0, min(h, w-i)) {
            qq.senpai(val(h-j-1, i+j));
        }
        up.senpai(_add_or(qq));
    }
    //query for down diagonals
    uwu(i, h, 0) {
        qq.clear();
        owo(j, 0, min(h-i, w)) {
            qq.senpai(val(i+j, j));
        }
        down.senpai(_add_or(qq));
    }
    owo(i, 1, w) {
        qq.clear();
        owo(j, 0, min(h, w-i)) {
            qq.senpai(val(j, i+j));
        }
        down.senpai(_add_or(qq));
    }
    vector<int> preup;
    owo(i, 0, up.size()) {
        if(i==0)preup.senpai(_add_xor({up[i]}));
        else {
            preup.senpai(_add_xor({up[i], preup[i-1]}));
        }
    }
    vector<int> predown;
    owo(i, 0, down.size()) {
        if(i==0)predown.senpai(_add_xor({down[i]}));
        else {
            predown.senpai(_add_xor({down[i], predown[i-1]}));
        }
    }
    int upval = 0;
    int downval = 0;
    owo(i, 0, preup.size()-d) {
        qq.clear();
        owo(j, i, i+d) {
            qq.senpai(preup[j]);
        }
        if(i==0) {
            upval = _add_or({_add_and(qq)});
        }else {
            upval = _add_or({upval, _add_and(qq)});
        }
    }
    owo(i, 0, predown.size()-d) {
        qq.clear();
        owo(j, i, i+d) {
            qq.senpai(predown[j]);
        }
        if(i==0) {
            downval = _add_or({_add_and(qq)});
        }else {
            downval = _add_or({downval, _add_and(qq)});
        }
    }
    return _add_and({upval, downval});
}
void construct_network(int H, int W, int K) {
    h = H;
    w = W;
    k = K;
    cnt = h*w;
    nxt = h*w;
    if(w+h-2==k) {
        solve(k);
    }
    else _add_and({solve(k), _add_not(solve(k+1))});
}
/*int n, m, f;
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>f;
    owo(i, 0, n) {
        owo(j, 0, m) {
            cin>>arr[i*m+j];
        }
    }
    construct_network(n, m, f);
    cout<<(arr[--nxt])<<"\n";
    return 0;
}*/

Compilation message

vision.cpp: In function 'int solve(int)':
vision.cpp:3:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a);i<(b); ++i)
                                    ^
vision.cpp:95:5: note: in expansion of macro 'owo'
     owo(i, 0, up.size()) {
     ^~~
vision.cpp:3:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a);i<(b); ++i)
                                    ^
vision.cpp:102:5: note: in expansion of macro 'owo'
     owo(i, 0, down.size()) {
     ^~~
vision.cpp:3:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a);i<(b); ++i)
                                    ^
vision.cpp:110:5: note: in expansion of macro 'owo'
     owo(i, 0, preup.size()-d) {
     ^~~
vision.cpp:3:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a);i<(b); ++i)
                                    ^
vision.cpp:121:5: note: in expansion of macro 'owo'
     owo(i, 0, predown.size()-d) {
     ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 6 ms 768 KB Output is correct
17 Correct 6 ms 896 KB Output is correct
18 Correct 5 ms 896 KB Output is correct
19 Correct 4 ms 768 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 0 ms 256 KB Output is correct

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB on inputs (0, 0), (1, 1), expected 0, but computed 1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 2296 KB on inputs (126, 120), (176, 169), expected 0, but computed 1
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
6 Halted 0 ms 0 KB -