제출 #70461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70461		funcsr	무지개나라 (APIO17_rainbow)	C++17	0 / 100	6 ms	640 KiB

rainbow

#include "rainbow.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <map>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};
struct UF {
  vector<int> U, R;
  UF(int N) {
    rep(i, N) U.pb(i), R.pb(1);
  }
  int find(int x) {if (U[x]==x)return x;return U[x]=find(U[x]); }
  void unite(int x, int y) {
    x=find(x),y=find(y);if(x==y)return;if(R[x]<R[y])swap(x,y);U[y]=x;R[x]+=R[y];
  }
};

vector<P> pos, yoko, tate, blocks;
vector<pair<P, P> > area;

void init(int H, int W, int sr, int sc, int M, char *S) {
  int y = sr-1, x = sc-1;
  pos.pb(P(x, y));
  blocks.pb(P(x, y));
  rep(i, M) {
    if (S[i] == 'N') y--;
    if (S[i] == 'S') y++;
    if (S[i] == 'W') x--;
    if (S[i] == 'E') x++;
    pos.pb(P(x, y));
    pos.pb(P(x+1, y));
    pos.pb(P(x, y+1));
    pos.pb(P(x+1, y+1));
    blocks.pb(P(x, y));
  }
  sort(all(pos)); uniq(pos);
  sort(all(blocks)); uniq(blocks);
  UF uf(pos.size());

  P m(x, y);
  map<P, bool> mp[4];
  y = sr-1, x = sc-1;
  rep(i, M) {
    if (S[i] == 'N') y--;
    if (S[i] == 'S') y++;
    if (S[i] == 'W') x--;
    if (S[i] == 'E') x++;
    mp[2][P(x, y)] = true;
    mp[3][P(x, y)] = true;
    mp[0][P(x+1, y)] = true;
    mp[3][P(x+1, y)] = true;
    mp[1][P(x, y+1)] = true;
    mp[2][P(x, y+1)] = true;
    mp[0][P(x+1, y+1)] = true;
    mp[1][P(x+1, y+1)] = true;
    uf.unite(index(pos, P(x, y)), index(pos, P(x+1, y)));
    uf.unite(index(pos, P(x, y)), index(pos, P(x, y+1)));
    uf.unite(index(pos, P(x, y)), index(pos, P(x+1, y+1)));
    m = min(m, P(x, y));
  }
  vector<P> repr(pos.size(), P(INF, INF));
  for (P p : pos) repr[uf.find(index(pos, p))] = min(repr[uf.find(index(pos, p))], p);

  rep(r, pos.size()) {
    if (repr[r] == P(INF, INF)) continue;
    int x = repr[r]._1, y = repr[r]._2;
    int minx=x,maxx=x,miny=y,maxy=y;
    int dir = 2;
    while (true) {
      minx=min(minx,x);
      maxx=max(maxx,x);
      miny=min(miny,y);
      maxy=max(maxy,y);
      if (mp[(dir+3)%4][P(x, y)]) dir=(dir+3)%4;
      else if (mp[dir][P(x, y)]) ;
      else if (mp[(dir+1)%4][P(x, y)]) dir=(dir+1)%4;
      else abort();
      if (dir == 0) yoko.pb(P(x-1, y));
      if (dir == 2) yoko.pb(P(x, y));
      if (dir == 1) tate.pb(P(x, y-1));
      if (dir == 3) tate.pb(P(x, y));
      x += DX[dir], y += DY[dir];
      if (P(x, y) == m) break;
    }
    area.pb(make_pair(P(minx,maxx), P(miny,maxy)));
  }
}

int colour(int miny, int minx, int maxy, int maxx) {
  miny--, minx--;
  int w = maxx-minx+1, h = maxy-miny+1;
  bool none = true;
  for (P p : blocks) if (minx <= p._1 && p._1 < maxx && miny <= p._2 && p._2 < maxy) none = false;
  if (none) return 1;

  //cout<<"w="<<w<<", h="<<h<<"\n";
  int e = 2*(w-1+h-1), v = 2*w+2*h-4, c = 1;
  for (P p : pos) if (minx < p._1 && p._1 < maxx && miny < p._2 && p._2 < maxy) v++;
  for (P p : yoko) if (minx <= p._1 && p._1 < maxx && miny < p._2 && p._2 < maxy) e++;
  for (P p : tate) if (minx < p._1 && p._1 < maxx && miny <= p._2 && p._2 < maxy) e++;
  for (auto p : area) if (minx < p._1._1 && p._1._2 < maxx && miny < p._2._1 && p._2._2 < maxy) c++;
  //cout<<"e="<<e<<", v="<<v<<", c="<<c<<"\n";
  return e-v+c-1;
}

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
rainbow.cpp:87:3: note: in expansion of macro 'rep'
   rep(r, pos.size()) {
   ^~~

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