제출 #1238884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238884		santi3223	Mosaic (IOI24_mosaic)	C++20	37 / 100	1033 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;
	}
	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;
}
*/

• 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: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22