Submission #1065260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065260		pcc	Soccer Stadium (IOI23_soccer)	C++17	2 / 100	1 ms	348 KiB

soccer

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2022;

int N;
pii row[mxn][mxn],col[mxn][mxn];
int rsum[mxn],csum[mxn];
int arr[mxn][mxn];

int rect(int sr,int er,int sc,int ec){
	return arr[er][ec]-arr[sr-1][ec]-arr[er][sc-1]+arr[sr-1][sc-1];
}

int biggest_stadium(int NN, std::vector<std::vector<int>> F){
	N = NN;
	int cnt = 0;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++)arr[i+1][j+1] = F[i][j],cnt += !F[i][j];
	}
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			arr[i][j] ^= 1;
			if(arr[i][j])rsum[i]++,csum[j]++;
			arr[i][j] = arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1]+arr[i][j];
		}
	}
	for(int i = 1;i<=N;i++){
		int lp = 1;
		for(int j = 1;j<=N;j++){
			if(F[i-1][j-1])lp = j+1;
			else col[i][j].fs = lp;
		}
		int rp = N;
		for(int j = N;j>=1;j--){
			if(F[i-1][j-1])rp = j-1;
			else col[i][j].sc = rp;
		}
	}
	for(int i = 1;i<=N;i++){
		int lp = 1;
		for(int j = 1;j<=N;j++){
			if(F[j-1][i-1])lp = j+1;
			else row[j][i].fs = lp;
		}
		int rp = N;
		for(int j = N;j>=1;j--){
			if(F[j-1][i-1])rp = j-1;
			else row[j][i].sc = rp;
		}
	}
	for(int i = 1;i<=N;i++)rsum[i] += rsum[i-1],csum[i]+=csum[i-1];

	/*
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			cerr<<col[i][j].fs<<' ';
		}cerr<<endl;
	}cerr<<endl;

	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			cerr<<col[i][j].sc<<' ';
		}cerr<<endl;
	}cerr<<endl;

	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			cerr<<row[i][j].fs<<' ';
		}cerr<<endl;
	}cerr<<endl;

	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			cerr<<row[i][j].sc<<' ';
		}cerr<<endl;
	}cerr<<endl;
	for(int i = 1;i<=N;i++)cerr<<rsum[i]<<' ';cerr<<endl;
	for(int i = 1;i<=N;i++)cerr<<csum[i]<<' ';cerr<<endl;
	*/


	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			if(F[i-1][j-1])continue;
			auto [sr,er] = row[i][j];
			auto [sc,ec] = col[i][j];
			int sum = rsum[er]-rsum[sr-1]+csum[ec]-csum[sc-1]-rect(sr,er,sc,ec);
			if(sum != cnt){
				cerr<<"WA! : "<<i<<' '<<j<<":"<<sum<<endl;
				return 0;
			}
		}
	}
	return cnt;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 2 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30