Submission #197337

#	Time	Username	Problem	Language	Result	Execution time	Memory
197337		dndhk	Plus Minus (BOI17_plusminus)	C++14	100 / 100	252 ms	13416 KiB

plusminus

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAX_N = 200000;
const int MAX_K = 18;
const ll MOD = 1000000007;

int N, M, K;
struct S{
	int type, x, y;
};
vector<S> vt;
ll ans;

ll multi(ll x, ll y){
	if(y==0)	return 1;
	if(y==1)	return x%MOD;
	ll m = multi(x, y/2);
	if(y%2){
		return (m*m%MOD)*x%MOD;
	}return (m*m)%MOD;
}

map<int, int> mp;
vector<int> v;

void solve(){
	while(!v.empty()){
		mp[v.back()] = 0;
		v.pop_back();
	}
	for(int i=0; i<vt.size(); i++){
		S now = vt[i];
		if(now.x%2==0){
			now.type*=(-1);
		}	
		if(mp[now.y]==0){
			v.pb(now.y);
			mp[now.y] = now.type;
		}else if(mp[now.y]!=now.type){
			return;
		}
	}
	ll two = multi(2LL, (ll)M - (ll)v.size());
	ans = (ans + two) % MOD;
}


int main(){
	scanf("%d%d%d", &N, &M, &K);
	for(int i=0; i<K; i++){
		getchar();
		char c; int a, b;
		scanf("%c %d %d", &c, &a, &b);
		if(c=='+'){
			vt.pb({1, a, b});
		}else{
			vt.pb({-1, a, b});
		}
	}
	solve();
	for(int i=0; i<K; i++){
		int tmp = vt[i].x; vt[i].x = vt[i].y; vt[i].y = tmp;
	}
	int tmp = N; N = M; M = tmp;
	solve();
	bool tf1 = true, tf2 = true;
	for(int i=0; i<vt.size(); i++){
		if((vt[i].x+vt[i].y+(vt[i].type+1)/2)%2){
			tf1 = false;
		}else{
			tf2 = false;
		}
	}
	if(tf1){
		ans = (ans + MOD - 1) % MOD;
	}if(tf2){
		ans = (ans + MOD - 1) % MOD;
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'void solve()':
plusminus.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
plusminus.cpp: In function 'int main()':
plusminus.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
plusminus.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %d %d", &c, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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