Submission #400781

#	Time	Username	Problem	Language	Result	Execution time	Memory
400781		my99n	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	2 ms	588 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

int a[3][200100];
set<pair<int,int>> s[5];


void init(int R, int C, int sr, int sc, int M, char *S) {
  a[sr][sc] = 1;
  for (int i = 0; i < M; i++) {
    if (S[i] == 'N') sr--;
    if (S[i] == 'S') sr++;
    if (S[i] == 'W') sc--;
    if (S[i] == 'E') sc++;
    a[sr][sc] = 1;
  } 

  // for (int i = 1; i <= R; i++) {
  //   for (int j = 1; j <= C; j++) {
  //     cout << a[i][j];
  //   } cout << endl;
  // }
  
  int cnt1 = 1, cnt2 = 1, cnt3 = 1;
  if (a[1][1]) s[1].insert({1, cnt1++});
  if (a[2][1]) s[2].insert({1, cnt2++});
  if (a[1][1] and a[2][1]) s[3].insert({1, cnt3++});
  for (int i = 2; i <= C; i++) {
    if (a[1][i-1] == 0 and a[1][i] == 1) s[1].insert({i, cnt1++});
    if (a[2][i-1] == 0 and a[2][i] == 1) s[2].insert({i, cnt2++});
    if (a[1][i-1] != 1 or a[2][i-1] != 1) {
      if (a[1][i] == 1 and a[2][i] == 1) s[3].insert({i, cnt3++});
    }
  }

  // for (auto x : s[1]) {
    // cout << x.first << ' ' << x.second << endl;
  // }

}

int colour(int ar, int ac, int br, int bc) {
  int ans = -1;
  if (ar == br) {
    if (s[ar].empty()) return 1;
    auto first = s[ar].lower_bound({ac, 0});
    auto second = s[ar].upper_bound({bc, 0});
    second--;
    // cerr << second->second  << ' ' <<  first->second << endl;
    ans = second->second - first->second + 2;
    if (a[ar][ac]) ans--;
    if (a[ar][bc]) ans--;
  }
  else {
    if (s[3].empty()) return 1;
    auto first = s[3].lower_bound({ac, 0});
    auto second = s[3].upper_bound({bc, 0});
    second--;
    ans = second->second - first->second + 2;
    if (a[1][ac] and a[2][ac]) ans--;
    if (a[1][bc] and a[2][bc]) ans--;
  }
  return ans;
}

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