oj.uz

답안 #637050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637050 2022-08-31T11:02:11 Z Joshua_Andersson Plus Minus (BOI17_plusminus) C++14
100 / 100
 139 ms 14552 KB 
#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <bits/stdc++.h>
using namespace std;

#define enablell 0

typedef long long ll;
typedef unsigned long long ull;
#if enablell
#define int ll
#define inf int(1e18)
#define float double
#else
const int inf = int(2e9);
#endif
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<int, int> p2;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vvp2> vvvp2;
typedef tuple<int, int, int> p3;
typedef vector<p3> vp3;
typedef vector<vp3> vvp3;
typedef vector<vvp3> vvvp3;
typedef tuple<int, int, int, int> p4;
typedef vector<p4> vp4;

#define _LOCAL _MSC_VER > 0
#if _LOCAL
#define gc() getchar()
#define popcount(x) __popcnt(x)
#define leading_zeros(x) _lzcnt_u32(x)
#define assert(x) debassert(x)
#else
#define popcount(x) __builtin__popcount(x)
#define leading_zeros(x) __builtin_clz(x)
#define gc() getchar_unlocked()
#if 0
#include <bits/extc++.h>
using namespace __gnu_pbds;
struct chash { // large odd number for C
    const uint64_t C = ll(4e18 * acos(0)) | 71;
    ll operator()(ll x) const { return x; }
};
//typedef __gnu_pbds::gp_hash_table<int, null_type, chash> h;
#endif

#endif

#define CIN_IN 1
#define FILE_TC 0
#if FILE_TC
ifstream filein("C:\\Users\\Matis\\source\\repos\\Comp prog\\x64\\Debug\\in.txt");
#define cin filein
//ifstream cin("C:\\Users\\Matis\\desktop\\po-two\\swedish-olympiad-2014\\");
void fast() {}
#else
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#endif

#if !FILE_TC && !CIN_IN
inline void read(int& v) { v = 0; int sign = 1; char c = gc(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = gc()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } v *= sign; }
inline void read(int& u, int& v) { read(u); read(v); }
//inline void read(int& v) { char c; while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } }
inline void read(string& s) { char c; while ((c = gc()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } }
#else
template <typename T> inline void read(T& a) { cin >> a; }
template <typename T> inline void read(T& a, T& b) { cin >> a >> b; }
template <typename T> inline void read(T& a, T& b, T& c) { cin >> a >> b >> c; }
#endif
template <typename T> inline void write(T& a) { cout << (a) << "\n"; }
#define quit cout << endl; _Exit(0);
#define dread(type, a) type a; read(a)
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#ifdef _DEBUG
#define noop cout << "";
#define deb __debugbreak();
#define debassert(expr) if (!(expr)) deb;
#define debif(expr) if(expr) deb;
#else
#define noop ;
#define deb ;
#define debassert(expr) ;
#define debif(expr) ;
#endif

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)
#define perr(i, low, high) for (int i = high-1; i >= low; i--)

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define revall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define within(a, b, c, d) (a >= 0 && a < b && c >= 0 && c < d)
#define sz(container) ((int)container.size())
#define mp(a,b) (make_pair(a,b))
#define first(a) (*begin(a))
#define indexpair(p, i) ((i==0)?p.first:p.second)
#define chmax(a,b) ((a)=max((a),b))
#define chmin(a,b) ((a)=min((a),b))

#define ceildiv(x,y) ((x + y - 1) / y)
#define fract(a) (a-floor(a))

template <typename T, typename U> inline void operator+=(pair<T, U>& l, const pair<T, U>& r) { l = { l.first + r.first,l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator+(const pair<T, U> l, const pair<T, U> r) { return { l.first + r.first, l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator-(const pair<T, U> l, const pair<T, U> r) { return { l.first - r.first, l.second - r.second }; }
template <typename T, typename U> inline pair<T, U> operator*(const pair<T, U> l, const int m) { return { l.first * m, l.second * m }; }
template <typename Out> inline void split(const string& s, char delim, Out result) { istringstream iss(s); string item; while (getline(iss, item, delim)) { *result++ = item; } }
inline vector<string> split(const string& s, char delim) { vector<string> elems; split(s, delim, back_inserter(elems)); return elems; }

#if 1
auto Start = chrono::high_resolution_clock::now();
#define elapsedmillis() (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count())
#define rununtil(time) if (elapsedmillis() >= time) break;
random_device rd;
mt19937 rng(rd());
#endif
const int mod = 1e9 + 7;

// a^b mod m
long long binpow(long long a, long long b, long long m)
{
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

struct point
{
    int x;
    int y;
    int sign;
};

bool doublecount = true;

ll solve(int n, int m, vector<point>& points)
{

    map<ll, vp2> rows;
    map<ll, vp2> rowsminus;
    repe(p, points)
    {
        rows[p.y].emplace_back(p.x, p.sign);
    }

    int lockedrows = 0;
    repe(row, rows)
    {
        int start = (row.second[0].first + row.second[0].second) % 2;
        bool works = true;
        repp(i, 1, row.second.size()) works &= (row.second[i].first+row.second[i].second)%2 == start;
        if (!works)
        {
            doublecount = false;
            return 0;
        }
        lockedrows++;
    }

    return binpow(2, m - lockedrows, mod);
}



int32_t main()
{
    fast();
    
    
    dread3(int, n, m, k);

    vector<point> samples(k);
    rep(i, k)
    {
        char c;
        cin >> c;
        samples[i].sign = c=='+';
        cin >> samples[i].x;
        cin >> samples[i].y;
    }

    ll ans = solve(n, m, samples);
    rep(i, k) swap(samples[i].x, samples[i].y);
    ans += solve(m, n, samples);

    if (doublecount)
    {
        if (k == 0) ans = (((ans - 2) % mod) + mod) % mod;
        else ans = (((ans - 1) % mod) + mod) % mod;
    }
    cout << ans;
    quit;

    /*int ans = 0;
    rep(mask, (1 << (n * m)))
    {
        vvi grid(n, vi(m));
        int c = 0;
        rep(i, n)
        {
            rep(j, m)
            {
                grid[i][j] = (mask & (1 << (c++)))>0;
            }
        }

        bool works = true;
        rep(i, n-1)
        {
            rep(j, m-1)
            {
                int s = 0;

                s += grid[i][j];
                s += grid[i+1][j];
                s += grid[i][j+1];
                s += grid[i+1][j+1];
                if (s != 2)
                {
                    works = false;
                }
            }

            
        }

        if (works)
        {
            rep(i, n)
            {
                rep(j, m)
                {
                    cout << (grid[i][j] ? '+' : '-');
                }
                cout << "\n";
            }
            ans++;
            cout << "#########\n";
        }
        
    }
    cout << ans;
*/


    quit;
}

Compilation message

plusminus.cpp: In function 'll solve(int, int, std::vector<point>&)':
plusminus.cpp:106:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 | #define repp(i, low, high) for (int i = low; i < high; i++)
......
  180 |         repp(i, 1, row.second.size()) works &= (row.second[i].first+row.second[i].second)%2 == start;
      |              ~~~~~~~~~~~~~~~~~~~~~~~            
plusminus.cpp:180:9: note: in expansion of macro 'repp'
  180 |         repp(i, 1, row.second.size()) works &= (row.second[i].first+row.second[i].second)%2 == start;
      |         ^~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 336 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 32 ms 3740 KB Output is correct
17 Correct 31 ms 3660 KB Output is correct
18 Correct 32 ms 3668 KB Output is correct
19 Correct 31 ms 3680 KB Output is correct
20 Correct 33 ms 3672 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 32 ms 3740 KB Output is correct
17 Correct 31 ms 3660 KB Output is correct
18 Correct 32 ms 3668 KB Output is correct
19 Correct 31 ms 3680 KB Output is correct
20 Correct 33 ms 3672 KB Output is correct
21 Correct 92 ms 9556 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 84 ms 9528 KB Output is correct
24 Correct 97 ms 9532 KB Output is correct
25 Correct 101 ms 9552 KB Output is correct
26 Correct 118 ms 12172 KB Output is correct
27 Correct 97 ms 12180 KB Output is correct
28 Correct 98 ms 12168 KB Output is correct
29 Correct 139 ms 12244 KB Output is correct
30 Correct 136 ms 14552 KB Output is correct