oj.uz

답안 #1066703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066703 2024-08-20T05:08:46 Z kunzaZa183 Plus Minus (BOI17_plusminus) C++17
12 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
signed main() {
	//cin.tie(0)->sync_with_stdio(0);

	int n,m,k;
	cin>>n>>m>>k;

	//plus = 0, minus = 1

	vector<tuple<int,int,char>> vtiic(k);
	vector<vector<int>> row(n,vector<int>(2,1)),col(m,vector<int>(2,1));
	vector<int> sumr(n),sumc(m);
	for(int i = 0; i < k; i++) {
		auto &[a,b,c] = vtiic[i];
		cin>>c>>a>>b;
		a--,b--;
		if(c=='+') {
			row[a][1 - b%2] = 0;
			col[b][1 - a%2] = 0;
		} else {
			row[a][b%2] = 0;
			col[b][a%2] = 0;
		}
	}

	const int mod = 1e18+7;

	for(int i =0; i < n;i++){
		sumr[i] = accumulate(row[i].begin(),row[i].end(),0);
//		cout<<sumr[i]<<'\n';
	}
	for(int i = 0; i < m;i++) {
		sumc[i] = accumulate(col[i].begin(),col[i].end(),0);
//		cout<<sumc[i]<<'\n';
	}
	vector<int> sufrow(n + 1),sufcol(m + 1);
	sufrow[n] = 1,sufcol[m] = 1;
	

	for(int i = n-1;i>=0;i--) {
		sufrow[i] = sufrow[i+1] * sumr[i];
		sufrow[i] %= mod;
	}

	for(int i = m-1;i>=0;i--) {
		sufcol[i] = sufcol[i+1] * sumc[i];
		sufcol[i] %= mod;
		//cout<<sufcol[i]<<" "<<i<<"\n";
	}

	//+even +odd
	vector<int> ok;
	ok.push_back(1);
	ok.push_back(1);


	int small = 0;
	for(int i = 0; i < n - 1;i++) {
		int coef = 0;
		if(i%2==0){
			if(row[i][0] && ok[0] && row[i+1][0])
				coef++;
			if(row[i][1] && ok[1] && row[i+1][1])
				coef++;
		} else {
			if(row[i][0] && row[i+1][0] && ok[1])
				coef++;
			if(row[i][1] && row[i+1][1] && ok[0])
				coef++;
		}

		small += coef * sufrow[i+2] % mod;
		small %= mod;

		if(sumr[i] == 1){
			if(i%2==0) {
				if(row[i][0])
					ok[1] = 0;
				else
					ok[0] = 0;
			} else {
				if(row[i][0])
					ok[0] = 0;
				else
					ok[1] = 0;
			}
		} else if(sumr[i] == 0) {
			ok[0] = 0,ok[1] = 0;
		}
	}

	ok = vector<int>(2,1);
	for(int i = 0; i < m - 1;i++) {
		int coef = 0;
		if(i%2==0){
			if(col[i][0] && col[i+1][0] && ok[1])
				coef++;
			if(col[i][1] && col[i+1][1] && ok[0])
				coef++;
		} else {
			if(col[i][0] && col[i+1][0] && ok[1])
				coef++;
			if(col[i][1] && col[i+1][1] && ok[0])
				coef++;
		}

		small += coef * sufcol[i+2] % mod;
		small %= mod;

		if(sumc[i] == 1){
			if(i%2==0) {
				if(col[i][0])
					ok[1] = 0;
				else
					ok[0] = 0;
			} else {
				if(col[i][0])
					ok[0] = 0;
				else
					ok[1] = 0;
			}
		} else if (sumc[i]==0) {
			ok[0] = 0,ok[1] = 0;
		}
	}

	ok = vector<int>(2,1);
	for(int i = 0; i < k;i++){
		auto [a,b,c] = vtiic[i];
		if((a + b) % 2 == 0) {
			if(c=='+')
				ok[1] = 0;
			else
				ok[0] = 0;
		} else {
			if(c=='+')
				ok[0] = 0;
			else
				ok[1] = 0 ;
		}
	}

	small += accumulate(ok.begin(),ok.end(),0);
	small %= mod;

	cout<<small<<"\n";

//	cout<<"DEBUG\n";
//	for(auto a:sufrow)
//		cout<<a<<"\n";
//	cout<<"\n";
//	for(auto a:sufcol)
//		cout<<a<<"\n";
}

Compilation message

plusminus.cpp: In function 'int main()':
plusminus.cpp:27:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |  const int mod = 1e18+7;
      |                  ~~~~^~

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 504 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 504 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -