oj.uz

Submission #1065260

# Submission time Handle Problem Language Result Execution time Memory
1065260 2024-08-19T05:05:27 Z pcc Soccer Stadium (IOI23_soccer) C++17
2 / 100
 1 ms 348 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 1 ms 344 KB ok
3 Partially correct 0 ms 344 KB partial
4 Partially correct 0 ms 348 KB partial
5 Partially correct 1 ms 348 KB partial
6 Partially correct 0 ms 348 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Partially correct 0 ms 344 KB partial
12 Partially correct 0 ms 344 KB partial
13 Correct 0 ms 348 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Partially correct 0 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Partially correct 1 ms 348 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 348 KB partial
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Partially correct 0 ms 348 KB partial
12 Partially correct 0 ms 344 KB partial
13 Partially correct 0 ms 344 KB partial
14 Correct 0 ms 348 KB ok
15 Incorrect 0 ms 348 KB wrong
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 1 ms 348 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 0 ms 348 KB partial
14 Partially correct 0 ms 344 KB partial
15 Partially correct 0 ms 344 KB partial
16 Correct 0 ms 348 KB ok
17 Incorrect 0 ms 348 KB wrong
18 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 1 ms 348 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Partially correct 0 ms 348 KB partial
14 Partially correct 0 ms 344 KB partial
15 Partially correct 0 ms 344 KB partial
16 Correct 0 ms 348 KB ok
17 Incorrect 0 ms 348 KB wrong
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB partial
2 Correct 1 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Incorrect 0 ms 348 KB wrong
8 Halted 0 ms 0 KB -