#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>
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}, DY[4]={0,-1,0,1};
struct UF {
vector<int> U, R;
int C;
UF(int N) {
rep(i, N) U.pb(i), R.pb(1);
C = N;
}
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];
C--;
}
};
int H, W;
bool bad[50][50];
int id[50][50];
vector<int> both[4], both2[4];
bool yo[4][200000];
int SX, SY;
string T;
void init(int HH, int WW, int sr, int sc, int M, char *S) {
SX=sc-1,SY=sr-1;T=string(S, S+M);
H = HH, W = WW;
if (H == 2) {
map<P, bool> bad;
int y = sr-1, x = sc-1;
bad[P(x, y)] = true;
rep(i, M) {
if (S[i] == 'N') y--;
if (S[i] == 'S') y++;
if (S[i] == 'W') x--;
if (S[i] == 'E') x++;
bad[P(x, y)] = true;
}
rep(S, 1<<H) {
rep(x, W) {
bool all = true;
rep(y, H) if ((S>>y)&1 && !bad[P(x,y)]) all = false;
yo[S][x] = all;
}
rep(x, W) if (yo[S][x]) both[S].pb(x);
rep(x, W-1) if (yo[S][x]&&yo[S][x+1]) both2[S].pb(x);
}
}
else if (W <= 50 && H <= 50) {
int y = sr-1, x = sc-1;
bad[x][y] = true;
rep(i, M) {
if (S[i] == 'N') y--;
if (S[i] == 'S') y++;
if (S[i] == 'W') x--;
if (S[i] == 'E') x++;
bad[x][y] = true;
}
}
}
int colour(int ar, int ac, int br, int bc) {
ar--, ac--, br--, bc--;
if (H == 2) {
int S = 0;
for (int y=ar; y<=br; y++) S |= 1<<y;
int l = ac, r = bc;
int s = index(both[S], r+1)-index(both[S], l);
if (s==0)return 1;
s -= index(both2[S], r)-index(both2[S], l);
s++;
if (yo[S][l]) s--;
if (yo[S][r]) s--;
return s;
}
else if (false) {
//else if (W <= 50 && H <= 50) {
int V = 0;
for (int x=ac; x<=bc; x++) {
for (int y=ar; y<=br; y++) {
if (!bad[x][y]) id[x][y] = V++;
else id[x][y] = -1;
}
}
UF uf(V);
for (int x=ac; x<=bc; x++) {
for (int y=ar; y<=br; y++) {
if (x+1<=bc && !bad[x][y] && !bad[x+1][y]) uf.unite(id[x][y], id[x+1][y]);
if (y+1<=br && !bad[x][y] && !bad[x][y+1]) uf.unite(id[x][y], id[x][y+1]);
}
}
return uf.C;
}
else {
br++,bc++;
//cout<<"Q=1\n";
// Q=1
map<P, bool> blocks;
int x = SX, y = SY;
blocks[P(x,y)] = true;
vector<P> inner;
vector<P> possible_tate, possible_yoko;
if (ac<=x&&x<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x, y));
if (ac<=x+1&&x+1<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x+1, y));
if (ac<=x&&x<=bc-1&&ar<=y&&y<=br) possible_yoko.pb(P(x, y));
if (ac<=x&&x<=bc-1&&ar<=y+1&&y+1<=br) possible_yoko.pb(P(x, y+1));
if (ac<=x&&x<=bc&&ar<=y&&y<=br) inner.pb(P(x, y));
for (char c:T) {
if (c == 'N') y--;
if (c == 'S') y++;
if (c == 'W') x--;
if (c == 'E') x++;
if (ac<=x&&x<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x, y));
if (ac<=x+1&&x+1<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x+1, y));
if (ac<=x&&x<=bc-1&&ar<=y&&y<=br) possible_yoko.pb(P(x, y));
if (ac<=x&&x<=bc-1&&ar<=y+1&&y+1<=br) possible_yoko.pb(P(x, y+1));
if (ac<=x&&x<=bc&&ar<=y&&y<=br) inner.pb(P(x, y));
blocks[P(x,y)] = true;
}
vector<P> tate, yoko;
for (P p : possible_tate) if (!blocks[P(p._1-1,p._2)]||!blocks[P(p._1,p._2)]) tate.pb(p);
for (P p : possible_yoko) if (!blocks[P(p._1,p._2-1)]||!blocks[P(p._1,p._2)]) yoko.pb(p);
for (int y=ar; y<=br-1; y++) tate.pb(P(ac, y)), tate.pb(P(bc, y));
for (int x=ac; x<=bc-1; x++) yoko.pb(P(x, ar)), yoko.pb(P(x, br));
sort(all(tate)); uniq(tate);
sort(all(yoko)); uniq(yoko);
vector<P> pts;
for (P p : tate) pts.pb(p), pts.pb(P(p._1, p._2+1));
for (P p : yoko) pts.pb(p), pts.pb(P(p._1+1, p._2));
sort(all(pts)); uniq(pts);
UF uf(pts.size());
for (P p : tate) {
int u = index(pts, p), v = index(pts, P(p._1, p._2+1));
uf.unite(u, v);
}
for (P p : yoko) {
int u = index(pts, p), v = index(pts, P(p._1+1, p._2));
uf.unite(u, v);
}
sort(all(inner)); uniq(inner);
UF uf2(inner.size());
rep(i, inner.size()) {
P p = inner[i];
rep(k, 4) {
int x = p._1+DX[k], y=p._2+DY[k];
if (!binary_search(all(inner), P(x,y))) continue;
int t = index(inner, P(x,y));
uf2.unite(i,t);
}
}
int e = tate.size()+yoko.size();
int v = pts.size();
int c = uf.C;
//cout<<"e="<<e<<", v="<<v<<", c="<<c<<"\n";
return e-v+c-uf2.C;
}
}
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i=0; i<(n); i++)
^
rainbow.cpp:174:5: note: in expansion of macro 'rep'
rep(i, inner.size()) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
352 ms |
29484 KB |
Output is correct |
| 4 |
Correct |
424 ms |
29948 KB |
Output is correct |
| 5 |
Correct |
445 ms |
29948 KB |
Output is correct |
| 6 |
Correct |
379 ms |
29948 KB |
Output is correct |
| 7 |
Correct |
436 ms |
29948 KB |
Output is correct |
| 8 |
Correct |
339 ms |
29948 KB |
Output is correct |
| 9 |
Correct |
388 ms |
29948 KB |
Output is correct |
| 10 |
Correct |
383 ms |
30012 KB |
Output is correct |
| 11 |
Correct |
404 ms |
30032 KB |
Output is correct |
| 12 |
Correct |
360 ms |
30032 KB |
Output is correct |
| 13 |
Correct |
398 ms |
30032 KB |
Output is correct |
| 14 |
Correct |
379 ms |
30180 KB |
Output is correct |
| 15 |
Correct |
320 ms |
30180 KB |
Output is correct |
| 16 |
Correct |
328 ms |
30180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
30180 KB |
Output is correct |
| 2 |
Correct |
322 ms |
30180 KB |
Output is correct |
| 3 |
Correct |
302 ms |
30180 KB |
Output is correct |
| 4 |
Correct |
432 ms |
33748 KB |
Output is correct |
| 5 |
Correct |
199 ms |
33748 KB |
Output is correct |
| 6 |
Correct |
215 ms |
33748 KB |
Output is correct |
| 7 |
Correct |
421 ms |
35520 KB |
Output is correct |
| 8 |
Correct |
73 ms |
35520 KB |
Output is correct |
| 9 |
Correct |
47 ms |
35520 KB |
Output is correct |
| 10 |
Incorrect |
34 ms |
35520 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
