Submission #1203024

#TimeUsernameProblemLanguageResultExecution timeMemory
1203024tamyteMosaic (IOI24_mosaic)C++20
27 / 100
153 ms23056 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; using ll = long long; vector<ll> check(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) { int Q = (int)T.size(); int N = (int)X.size(); vector<vector<int>> grid(N, vector<int>(N)); for (int i = 0; i < N; ++i) { grid[0][i] = X[i]; grid[i][0] = Y[i]; } for (int i = 1; i < N; ++i) { for (int j = 1; j < N; ++j) { if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1; else grid[i][j] = 0; } } vector<vector<ll>> dp(N, vector<ll>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { dp[i][j] = grid[i][j]; if (i > 0) dp[i][j] += dp[i - 1][j]; if (j > 0) dp[i][j] += dp[i][j - 1]; if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1]; } } std::vector<long long> C(Q, 0); for (int i = 0; i < Q; ++i) { int y1 = T[i]; int y2 = B[i]; int x1 = L[i]; int x2 = R[i]; ll res = 0; if (y1 > 0) res -= dp[y1 - 1][x2]; if (x1 > 0) res -= dp[y2][x1 - 1]; if (x1 > 0 && y1 > 0) res += dp[y1 - 1][x1 - 1]; res += dp[y2][x2]; C[i] = res; } return C; } 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) { int Q = (int)T.size(); int N = (int)X.size(); if (N <= 2) { return check(X, Y, T, B, L, R); } map<int, int> mp; int start = (X[1] + Y[1] == 0); if (start == 1) { mp[0]++; } vector<int> nX, nY; nX.push_back(start); nY.push_back(start); for (int i = 2; i < N; ++i) { nX.push_back((nX.back() + X[i] == 0)); if (nX.back() == 1) { mp[1 - i]++; } } for (int i = 2; i < N; ++i) { nY.push_back((nY.back() + Y[i] == 0)); if (nY.back() == 1) { mp[i - 1]++; } } // for (auto& u : mp) { // cout << u.first << " " << u.second << "\n"; // } // cout << "/\n"; start = (nX[1] + nY[1] == 0); vector<int> nnX{start}, nnY{start}; if (start == 1) { mp[0]++; } for (int i = 2; i < nX.size(); ++i) { nnX.push_back((nnX.back() + nX[i] == 0)); if (nnX.back() == 1) { mp[1 - i]++; } } for (int i = 2; i < nY.size(); ++i) { nnY.push_back((nnY.back() + nY[i] == 0)); if (nnY.back() == 1) { mp[i - 1]++; } } // for (auto& i : nX) { // cout << i << " "; // } // cout << endl; // for (auto& i : nY) { // cout << i << " "; // } // cout << endl; // for (auto& i : nnX) { // cout << i << " "; // } // cout << endl; // for (auto& i : nnY) { // cout << i << " "; // } // cout << endl; // for (auto& u : mp) { // cout << u.first << " " << u.second << "\n"; // } vector<ll> C(Q); for (int i = 0; i < Q; ++i) { int y1 = T[i]; int y2 = B[i]; int x1 = L[i]; int x2 = R[i]; if (y1 == 0 || x1 == 0) { if (y1 == 0) { C[i] = X[x1]; } else { C[i] = Y[y1]; } continue; } if (y1 == 1 || x1 == 1) { if (y1 == 1) { C[i] = nX[x1 - 1]; } else { C[i] = nY[y1 - 1]; } continue; } if (y1 == 2 || x1 == 2) { if (y1 == 2) { C[i] = nnX[x1 - 2]; } else { C[i] = nnY[y1 - 2]; } continue; } // cout << y1 << " " << x1 << " , " << y1 - x1 << endl; if (mp.count(y1 - x1)) { C[i] = 1; } else { C[i] = 0; } } // vector<ll> res = check(X, Y, T, B, L, R); // vector<vector<int>> grid(N, vector<int>(N)); // for (int i = 0; i < N; ++i) { // grid[0][i] = X[i]; // grid[i][0] = Y[i]; // } // for (int i = 1; i < N; ++i) { // for (int j = 1; j < N; ++j) { // if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1; // else grid[i][j] = 0; // } // } // for (auto& v : grid) { // for (auto& u : v) { // cout << u << " "; // } // cout << "\n"; // } // cout << "\n"; // for (int i = 0; i < Q; ++i) { // if (res[i] != C[i]) { //// cout << "WA at #" << i + 1 << " query, expected = " << res[i] << " , got = " << C[i] << endl;; //// cout << grid[T[i]][L[i]] << endl; // // } // } return C; } /* 10 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 10 0 1 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 */ /* 4 1 0 1 0 1 1 0 1 2 0 0 0 0 1 1 3 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...