C
出题人太善良了，加强到 \(10^5\) 都没问题。
考虑维护每条横线竖线两条对角线上被标记的点的个数，每次标记点后，判断是否有线上点全被标记。
再考虑如何将点编号转为坐标，记编号为 \(t\)，推柿子：
\[(x-1)\times n+y=t \]\[nx+y=t+n \]\[x=\frac{t+n-y}{n} \]等同于找到 \(y\) 使得：
\[n\mid t+n-y \]随便算就行，代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Pii = pair<int, int>;
const LL kMaxN = 2e3 + 5;
LL n, t, cnt[kMaxN][2], cnt2[2];
bool a[kMaxN];
Pii Calc(LL k) {
if (!(k % n)) {
return {(k - n) / n, n};
} else {
int y = k % n;
return {(k - y) / n, y};
}
}
signed main() {
cin >> n >> t;
for (LL i = 1, pty; i <= t; i++) {
cin >> pty;
Pii t = Calc(pty + n);
cnt[t.first][0]++, cnt[t.second][1]++;
cnt2[0] += t.first == t.second, cnt2[1] += t.first + t.second == n + 1;
(cnt[t.first][0] == n || cnt[t.second][1] == n || cnt2[0] == n || cnt2[1] == n) && (cout << i, exit(0), 0);
}
cout << -1;
}
D
线段 \([l1,r1]\) 和 \([l2,r2]\) 相交的条件是：\(r1\ge l2\)，扫一遍线段，考虑维护所有
标签：Atcoder,cnt,LL,kMaxN,second,cnt2,ABC355,first From： https://www.cnblogs.com/Livedreamyhy/p/18224981