제출 #1170915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170915		JelalTkm	Land of the Rainbow Gold (APIO17_rainbow)	C++20	0 / 100	1453 ms	1114112 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

const int Nqwe = 2e5 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;

vector<vector<int>> a(60, vector<int> (2e5 + 10));
vector<int> pref(2e5 + 10), pref1(2e5 + 10), pref2(2e5 + 10);
vector<bool> okw(2e5 + 10), ok1(2e5 + 10), ok2(2e5 + 10);
bool visited[60][Nqwe];
bool ok = 0;

bool check(int x1, int y1, int x2, int y2, int x, int y) {
  return (x >= x1 && x <= x2 && y >= y1 && y <= y2);
}

int colour(int x1, int y1, int x2, int y2) {
  if (!ok) {
    memset(visited, 0, sizeof visited);
    int ans = 0;
    for (int i = x1; i <= x2; i++) {
      for (int j = y1; j <= y2; j++) {
        if (!visited[i][j] && !a[i][j]) {
          ans++;
          queue<pair<int, int>> q;
          q.push({i, j});
          while (!q.empty()) {
            auto [u, v] = q.front();
            q.pop();
            if (check(x1, y1, x2, y2, u + 1, v) && !a[u + 1][v]) {
              visited[u + 1][v] = 1;
              q.push({u + 1, v});
            }
            if (check(x1, y1, x2, y2, u - 1, v) && !a[u - 1][v]) {
              visited[u - 1][v] = 1;
              q.push({u - 1, v});
            }
            if (check(x1, y1, x2, y2, u, v + 1) && !a[u][v + 1]) {
              visited[u][v + 1] = 1;
              q.push({u, v + 1});
            }
            if (check(x1, y1, x2, y2, u, v - 1) && !a[u][v - 1]) {
              visited[u][v - 1] = 1;
              q.push({u, v - 1});
            }
          }
        }
      }
    }
    return ans;
  } else {
    if (x1 != x2) {
      return (pref[y2] - pref[y1 - 1] + ((!a[x1][y2] | !a[x2][y2])) - okw[y1]);
    } else if (x1 == 1) {
      return (pref1[y2] - pref1[y1 - 1] + (!a[x1][y2]) - ok1[y1]);
    } else return (pref2[y2] - pref2[y2 - 1] + (!a[x1][y2]) - ok2[y1]);
  }

  return 0;
}

void init(int n, int m, int x, int y, int c, char *s) {
  if (n == 2)
    ok = 1;
  a[x][y] = 1;
  for (int i = 0; i < c; i++) {
    if (s[i] == 'N') x--;
    if (s[i] == 'S') x++;
    if (s[i] == 'W') y--;
    if (s[i] == 'E') y++;
    a[x][y] = 1;
  }

  if (ok) {
    for (int i = 1; i <= m; i++) {
      pref[i] = pref[i - 1];
      pref1[i] = pref1[i - 1];
      pref2[i] = pref2[i - 1];
      if (a[1][i] == 1 && a[2][i] == 1 && (i > 1 && (!a[1][i - 1] || !a[2][i - 1])))
        pref[i]++, okw[i] = 1;
      if (a[1][i] == 1 && (i > 1 && !a[1][i - 1]))
        pref1[i]++, ok1[i] = 1;
      if (a[2][i] == 1 && (i > 1 && !a[2][i - 1]))
        pref2[i]++, ok2[i] = 1;
    }
  }

  return;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {

//   }

//   return 0;
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26