https://ac.nowcoder.com/acm/contest/331/B

题解：

std

五子棋只需要计算同方向连续的五个子即可。

所以对于每次落子，我们只需要知道其4个方向(双向)连续的子数（只需要查找至多4*8个位置是否存在即可）。

需要利用一些简单的剪枝降低这个查找次数（比如遇到五子即退出，比如遇到不连续则continue之类）。

通过以上优化，使用set< pair<int,int> >来存放也不会超时。

否则可能需要一定的优化才行。

时间复杂度O(MlogM)O(Mlog⁡M)（使用平衡树比如set）或O(M)（如果使用哈希表的话）

#include <bits/stdc++.h>
using namespace std;
 
const int mn = 3e5 + 5;
 
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
 
int n;
unordered_map<int, bool> h[mn];
 
inline bool inbound(int x, int y) {
    return x <= n && x >= 1 && y <= n && y >= 1;
}
 
inline bool getColor(int x, int y) { return h[x][y]; }
 
inline int getNumberByWay(int k, int x, int y) {
    int s = 1;
    while (s <= 5) {
        int ux = x + dx[k] * s, uy = y + dy[k] * s;
        if (!inbound(x, y) || !h[ux].count(uy) ||
            getColor(x, y) != getColor(ux, uy))
            return s - 1;
        s++;
    }
    return s;
}
 
inline bool win(int x, int y, bool color) {
    h[x][y] = color;
    for (int i = 0; i < 4; i++) {
        if (getNumberByWay(i, x, y) + getNumberByWay(i + 4, x, y) + 1 >= 5)
            return 1;
    }
    return 0;
}
 
int m;
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (win(x, y, i % 2))
            puts("Y");
        else
            puts("N");
    }
}