Submission #1275885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275885		nariman_mt87	Plus Minus (BOI17_plusminus)	C++20	100 / 100	32 ms	2036 KiB

plusminus

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define lli long long int
#define pii pair<lli,lli>
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define se  second
#define fi first
#define nn '\n'
#define txt freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define T int T;cin>>T;while(T--)
#define ashar(x) fixed<<setprecision(x)
#define migmig ios_base::sync_with_stdio(0);cin.tie(0);
const int maxn= 1e6 + 1, mod = 1e9 + 7, v2 = (mod + 1) / 2;
lli pwm(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pwm(a * a , b / 2) : pwm(a * a, b / 2))); }
lli pw(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pw(a * a % mod, b / 2) % mod : pw(a * a % mod, b / 2) % mod)); }//a*pw(b,mod-2) == (a/b)%mod
int a[maxn], b[maxn], c[maxn], p[maxn];
int main() {
	migmig;
	int n, m, k; cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		char ch; int x, y; cin >> ch >> x >> y, x--, y--;
		a[i] = ch == '-', b[i] = x, c[i] = y, p[i] = i;
	}
	int ans = 0;
	for (int z = 0; z < 2; z++) {
		sort(p, p + k, [] (int i, int j) { return b[i] < b[j]; });
		long long po = pw(2, n); bool dbl = true;
		for (int h = 0, g; h < k; h = g) {
			int i = p[h], j, x = b[i], y = a[i] ^ c[i] & 1;
			bool yes = true;
			for (g = h + 1; g < k && b[j = p[g]] == x; g++)
				if ((a[j] ^ c[j] & 1) != y) {
					yes = false;
					break;
				}
			if (!yes) {
				po = 0;
				dbl = false;
				break;
			}
			po = po * v2 % mod;
			if ((y ^ x & 1) != z)
				dbl = false;
		}
		ans = (ans + po) % mod;
		if (dbl)
			ans = (ans - 1 + mod) % mod;
		swap(n, m);
		for (int i = 0; i < k; i++)
			swap(b[i], c[i]);
	}
	cout << ans << nn;
}

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