Submission #1226529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226529		ByeWorld	Treasure (different grader from official contest) (CEOI13_treasure2)	C++20	10 / 100	3 ms	1864 KiB

treasure

#include "treasure.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define que countTreasure
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 1e5+10;
const int SQRT = 450;
const int INF = 1e9+100;
const int LOG = 20;
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, pr[1010][1010];
bool ada[1010][1010];
ll pref[1010][1010], a[1010][1010];
map<array<int,4>, int> ma;
ll tot = 0;

int tre(int a, int b, int c, int d){
	array <int, 4> te = {a, b, c, d};
	if(ma.find(te) != ma.end()) return ma[te];

	tot += n*n - (c-a+1)*(d-b+1)+1;
	ma[te] = que(a,b,c,d);
	return ma[te];
}

void findTreasure (int N) {
	n = N;
	int las = 0, x, y;
	for(int i=1; i<=n/2+1; i++){ // kiri atas
		for(int j=1; j<=n/2+1; j++){
			// cout << i << ' ' << j << " kiritatas\n";
			pr[i][j] = tre(i,j, n,n);
			las = pr[i][j];
			if(i==n/2+1 && j==1) x = pr[i][j];
			if(i==n/2+1 && j==n/2+1) y = pr[i][j];
		}
	}
	for(int i=1; i<=n/2; i++){
		for(int j=1; j<=n/2; j++){
			int th = pr[i][j]-pr[i+1][j]-pr[i][j+1]+pr[i+1][j+1];
			ada[i][j] = th;
		}
	}
	
	// cout << tot << " tot\n";
	// kanan bawah
	for(int i=n; i>=n/2+1; i--){
		for(int j=n; j>=n/2+1; j--){
			if(i==n/2+1 && j==n/2+1) continue; // gk ush
			// cout << i << ' ' << j << " kananbwah\n";
			pr[i][j] = tre(1,1, i,j);
		}
	}
	int sum = 0;
	for(int i=n; i>=n/2+1; i--){
		for(int j=n; j>=n/2+1; j--){
			if(i==n/2+1 && j==n/2+1){
				ada[i][j] = las-sum; continue;
			}
			int th = pr[i][j]-pr[i-1][j]-pr[i][j-1]+pr[i-1][j-1];
			ada[i][j] = th;
			sum += th;
		}
	}

	int p = x-y;

	for(int i=n; i>=1; i--){
		for(int j=1; j<=n; j++){
			pref[i][j] = pref[i+1][j]+pref[i][j-1]-pref[i+1][j-1];
			if(i==n/2+1 && j==n/2) pref[i][j] += p;
			pref[i][j] += ada[i][j];
		}
	}
	for(int i=1; i<=n/2; i++){ // atas kanan
		for(int j=n; j>=n/2+1; j--){
			pref[i][j] = tre(i, 1, n, j);
		}
	}
	// for(int i=1; i<=n; i++){
	// 	for(int j=1; j<=n; j++){
	// 		cout << pref[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	// cout << " done\n";
	for(int i=n/2; i>=1; i--){ // atas kanan
		for(int j=n/2+1; j<=n; j++){
			int th = pref[i][j]-pref[i+1][j]-pref[i][j-1]+pref[i+1][j-1];
			ada[i][j] = th;
		}
	}

	// kiri bawah
	for(int i=1; i<=n; i++){
		for(int j=n; j>=1; j--){
			pref[i][j] = pref[i-1][j]+pref[i][j+1]-pref[i-1][j+1];
			pref[i][j] += ada[i][j];
		}
	}
	for(int i=n/2+1; i<=n; i++)
		for(int j=n/2; j>=1; j--)
			pref[i][j] = tre(1, j, i, n);

	for(int i=n/2+1; i<=n; i++){
		for(int j=n/2; j>=1; j--){
			int th = pref[i][j]-pref[i-1][j]-pref[i][j+1]+pref[i-1][j+1];
			ada[i][j] = th;
		}
	}


	// for(int i=1; i<=n; i++){
	// 	for(int j=1; j<=n; j++){
	// 		cout << ada[i][j];
	// 	}
	// 	cout << '\n';
	// }
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(ada[i][j])
				Report(i, j);
			
}

• Subtask 1: 10 / 100