제출 #562642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562642		SSRS	무지개나라 (APIO17_rainbow)	C++14	35 / 100	3075 ms	29548 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
int xmin, xmax, ymin, ymax;
set<pair<int, int>> vertex, edge_v, edge_h, face;
void init(int R, int C, int sr, int sc, int M, char *S){
  sr--;
  sc--;
  vector<int> x(M + 1), y(M + 1);
  x[0] = sr;
  y[0] = sc;
  for (int i = 0; i < M; i++){
    x[i + 1] = x[i];
    y[i + 1] = y[i];
    if (S[i] == 'N'){
      x[i + 1]--;
    }
    if (S[i] == 'S'){
      x[i + 1]++;
    }
    if (S[i] == 'E'){
      y[i + 1]++;
    }
    if (S[i] == 'W'){
      y[i + 1]--;
    }
  }
  xmin = sr;
  xmax = sr;
  ymin = sc;
  ymax = sc;
  for (int i = 1; i <= M; i++){
    xmin = min(xmin, x[i]);
    xmax = max(xmax, x[i]);
    ymin = min(ymin, y[i]);
    ymax = max(ymax, y[i]);
  }
  for (int i = 0; i <= M; i++){
    vertex.insert(make_pair(x[i], y[i]));
    edge_v.insert(make_pair(x[i], y[i]));
    edge_v.insert(make_pair(x[i] - 1, y[i]));
    edge_h.insert(make_pair(x[i], y[i]));
    edge_h.insert(make_pair(x[i], y[i] - 1));
    face.insert(make_pair(x[i], y[i]));
    face.insert(make_pair(x[i] - 1, y[i]));
    face.insert(make_pair(x[i], y[i] - 1));
    face.insert(make_pair(x[i] - 1, y[i] - 1));
  }
}
int colour(int ar, int ac, int br, int bc){
  ar--;
  ac--;
  int ans = 1;
  for (auto P : vertex){
    if (ar <= P.first && P.first < br && ac <= P.second && P.second < bc){
      ans--;
    }
  }
  for (auto P : edge_v){
    if (ar <= P.first && P.first < br - 1 && ac <= P.second && P.second < bc){
      ans++;
    }
  }
  for (auto P : edge_h){
    if (ar <= P.first && P.first < br && ac <= P.second && P.second < bc - 1){
      ans++;
    }
  }
  for (auto P : face){
    if (ar <= P.first && P.first < br - 1 && ac <= P.second && P.second < bc - 1){
      ans--;
    }
  }
  if (ar < xmin && xmax < br - 1 && ac < ymin && ymax < bc - 1){
    ans++;
  }
  return ans;
}

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