Submission #698239

#	Time	Username	Problem	Language	Result	Execution time	Memory
698239		Fidisk	Plus Minus (BOI17_plusminus)	C++14	0 / 100	2 ms	340 KiB

plusminus

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

#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;

map<ll,ll> cnt,cnt2;
ll sl,res,n,m,sl2,s[500009],x[500009],y[500009],t1,t2,t3,i,k,xbase,ybase;
char ch;

ll GTN(ll x,ll y) {
    if (y<0) return 0;
    if (y==0) {
        return 1;
    }
    else {
        ll tmp=GTN(x,y/2);
        if (y%2==0) {
            return (tmp*tmp)%mod;
        }
        else {
            return (((tmp*tmp)%mod)*x)%mod;
        }
    }
}

int main(){
    IO;
    #ifndef ONLINE_JUDGE
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    #else
    #endif
    cin>>n>>m>>k;
    for (i=1;i<=k;i++) {
        cin>>ch>>x[i]>>y[i];
        if (ch=='+') {
            s[i]=1;
        }
        else {
            s[i]=0;
        }
    }
    xbase=-1;
    //Try building up x-line
    for (i=1;i<=k;i++) {
        if (cnt[x[i]]==(s[i]^1^(1&y[i]))+1) {
            //Can't build x-line
            sl=-1;
            break;
        }
        else if (cnt[x[i]]==0) {
            sl++;
            cnt[x[i]]=(s[i]^(1&y[i]))+1;
            //Checker x-line check
            if (xbase==-2) {
                //Already nope
            }
            else if (((cnt[x[i]]-1)^(1&x[i]))==xbase||xbase==-1) {
                xbase=(cnt[x[i]]-1)^(1&x[i]);
            }
            else {
                //Can't do checker
                xbase=-2;
            }
        }
    }
    ybase=-1;
    //Try to build y-line
    for (i=1;i<=k;i++) {
        if (cnt2[y[i]]==(s[i]^1^(1&x[i]))+1) {
            //Can't build y-line
            sl2=-1;
            break;
        }
        else if (cnt2[y[i]]==0) {
            sl2++;
            cnt2[y[i]]=(s[i]^(1&x[i]))+1;
            //Checker y-line check
            if (ybase==-2) {
                //Already nope
            }
            else if (((cnt2[y[i]]-1)^(1&y[i]))==ybase||ybase==-1) {
                ybase=(cnt2[y[i]]-1)^(1&y[i]);
            }
            else {
                //Can't do checker
                ybase=-2;
            }
        }
    }
    if (sl>=0) {
        if (xbase>=-1) {
            res=(res+GTN(2,n-sl)*GTN(2,m-sl2))%mod;
        }
        else {
            res=(res+GTN(2,n-sl))%mod;
        }
    }
    //cout<<res<<'\n';
    if (sl2>=0) {
        if (ybase>=-1) {
            res=(res+GTN(2,n-sl)*GTN(2,m-sl2))%mod;
        }
        else {
            res=(res+GTN(2,n-sl))%mod;
        }
    }
    //cout<<res<<'\n';
    //Both x and y-line
    if (sl>=0&&sl2>=0) {
        res=(res-GTN(2,n-sl+m-sl2)+mod)%mod;
    }
    cout<<res<<'\n';
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46