Submission #1238900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238900		santi3223	Mosaic (IOI24_mosaic)	C++20	59 / 100	1025 ms	2162688 KiB

mosaic

#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
#define ll long long
#define vl vector<ll>
#define all(aaa) aaa.begin(), aaa.end()
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vb vector<bool>
#define ed "\n"
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R){
	bool tod0 = true;
	ff(i, 0, T.size()){
		if(T[i] == B[i] && T[i] == 0){
			continue;
		}
		else{
			tod0 = false;
			break;
		}
	}
	ll n = X.size();
	if(tod0){
		//cout << "TOD0" << ed;
		vl psum(n);
		psum[0] = X[0];
		ff(i, 1, n){
			psum[i] = psum[i-1]+X[i];
		}
		vl ans;
		ff(i, 0, T.size()){
			ll l = 0;
			if(L[i]-1 >= 0){
				l = psum[L[i]-1];
			}
			ans.pb(psum[R[i]]-l);
		}
		return ans;
	}
	bool inic0 = true;
	ff(i, 0, n){
		if(X[i] == Y[i] && X[i] == 0){
			continue;
		}
		else{
			inic0 = false;
			break;
		}
	}
	if(inic0){
		//cout << "INIC0" << ed;
		vl ans;
		ff(i, 0, T.size()){
			if(B[i] == 0 || R[i] == 0){
				ans.pb(0);
				continue;
			}
			if(T[i] == 0){
				T[i]++;
			}
			if(L[i]==0){
				L[i]++;
			}
			if((R[i]-L[i]+1) % 2 == 0){
				ll dist = R[i]-L[i]+1;
				ll cant = B[i]-T[i]+1;
				dist /= 2;
				ans.pb(dist*cant);
			}
			else{
				ll dist = R[i]-L[i];
				ll cant = B[i]-T[i]+1;
				dist /= 2;
				ll base = dist*cant;
				if(cant % 2 == 0){
					base += cant/2;
				}
				else if((L[i] % 2) == (T[i] % 2)){
					cant++;
					base += cant/2;
				}
				else{
					cant--;
					base += cant/2;
				}
				ans.pb(base);
			}
		}
		return ans;
	}
	bool sub6 = true;
	ff(i, 0, T.size()){
		if(T[i] == B[i] && L[i] == R[i]){
			continue;
		}
		else{
			sub6 = false;
		}
	}
	if(sub6){
		vector<vl> hori(3, vl(n)), verti(n, vl(3));
		hori[0][0] = Y[0];
		hori[1][0] = Y[1];
		hori[2][0] = Y[2];
		verti[0][0] = X[0];
		verti[0][1] = X[1];
		verti[0][2] = X[2];
		ff(i, 0, 3){
			ff(j, 0, n){
				if(i == 0){
					hori[i][j] = X[j];
					continue;
				}
				if(j == 0){
					continue;
				}
				if(hori[i][j-1] == 0 && hori[i-1][j] == 0){
					hori[i][j] = 1;
				}
				else{
					hori[i][j] = 0;
				}
			}
		}
		ff(i, 1, n){
			ff(j, 0, 3){
				if(j == 0){
					verti[i][j] = Y[i];
					continue;
				}
				if(verti[i][j-1] == 0 && verti[i-1][j] == 0){
					verti[i][j] = 1;
				}
				else{
					verti[i][j] = 0;
				}
			}
		}
		/*ff(i, 0, 3){
			ff(j, 0, n){
				cout << hori[i][j] << " ";
			}
			cout << ed;
		}
		cout << ed;
		ff(i, 0, n){
			ff(j, 0, 3){
				cout << verti[i][j] << " ";
			}
			cout << ed;
		}*/
		vl ans;
		ff(i, 0, T.size()){
			//cout << ed;
			ll x = L[i], y = T[i];
			if(x <= 2){
				ans.pb(verti[y][x]);
				continue;
			}
			if(y <= 2){
				ans.pb(hori[y][x]);
				continue;
			}
			//cout << "ORI " << y << " " << x << ed;
			ll minn = min(-1*(2-x), -1*(2-y));
			x -= minn;
			y -= minn;
			//cout << y << " " << x << ed;
			if(x <= 2){
				//cout << "V";
				ans.pb(verti[y][x]);
				continue;
			}
			if(y <= 2){
				ans.pb(hori[y][x]);
				continue;
			}
		}
		return ans;
		
	}
	if(n <= 5000){
		vector<vl> grid(n, vl(n));
		ff(j, 0, n){
			grid[0][j] = X[j];
		}
		ff(i, 0, n){
			grid[i][0] = Y[i];
		}
		ff(i, 1, n){
			ff(j, 1, n){
				if(grid[i][j-1] == 0 && grid[i-1][j] == 0){
					//cout << "NO";
					grid[i][j] = 1;
				}
				else{
					//cout << "YES";
					grid[i][j] = 0;
				}
			}
		}
		/*ff(i, 0, n){
			ff(j, 0, n){
				cout << grid[i][j] << " ";
			}
			cout << ed;
		}
		cout << ed << ed;*/
		vector<vl> psum(n, vl(n));
		ff(i, 0, n){
			ff(j, 0, n){
				if(j == 0){
					psum[i][j] = grid[i][j];
					continue;
				}
				psum[i][j] = psum[i][j-1]+grid[i][j];
			}
		}
		/*ff(i, 0, n){
			ff(j, 0, n){
				cout << psum[i][j] << " ";
			}
			cout << ed;
		}
		cout << ed;*/
		ff(j, 0, n){
			ff(i, 1, n){
				psum[i][j] += psum[i-1][j];
			}
		}
		/*ff(i, 0, n){
			ff(j, 0, n){
				cout << psum[i][j] << " ";
			}
			cout << ed;
		}
		cout << ed;*/
		ll q = T.size();
		vl ans;
		ff(i, 0, q){
			ll a = 0;
			if(L[i]-1 >= 0 && T[i]-1 >= 0){
				a = psum[T[i]-1][L[i]-1];
			}
			ll b = 0;
			if(T[i]-1 >= 0){
				b = psum[T[i]-1][R[i]];
			}
			ll c = 0;
			if(L[i]-1 >= 0){
				c = psum[B[i]][L[i]-1];
			}
			ll d = psum[B[i]][R[i]];
			//cout << a << " " << b << " " << c << " " << d << ed;
			ans.pb(d+a-b-c);
		}
		return ans;
	}
	
}
/*
int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &X[i]));
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Y[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> T(Q), B(Q), L(Q), R(Q);
  for (int k = 0; k < Q; k++)
    assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
  fclose(stdin);

  std::vector<long long> C = mosaic(X, Y, T, B, L, R);

  int S = (int)C.size();
  for (int k = 0; k < S; k++)
    printf("%lld\n", C[k]);
  fclose(stdout);

  return 0;
}
*/

Compilation message (stderr)

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:266:1: warning: control reaches end of non-void function [-Wreturn-type]
  266 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22