| 比赛 |
USACO2026 JAN G&P2 |
评测结果 |
WWWAWWWWWWWWWWWW |
| 题目名称 |
Supervision |
最终得分 |
6 |
| 用户昵称 |
LikableP |
运行时间 |
2.475 s |
| 代码语言 |
C++ |
内存使用 |
15.70 MiB |
| 提交时间 |
2026-01-24 11:05:42 |
显示代码纯文本
#include <cstdio>
#include <cctype>
#include <vector>
template <typename T> T read() {
T res = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return res * f;
}
typedef long long ll;
const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
ll pow2[MAXN];
void Initialize() {
pow2[0] = 1;
for (int i = 1; i <= MAXN - 10; ++i) {
pow2[i] = (pow2[i - 1] * 2) % MOD;
}
}
int n, d;
int place[MAXN], indentity[MAXN];
int couchCount;
ll ans;
int main() {
#ifdef LOCAL
freopen("!input.in", "r", stdin);
freopen("!output.out", "w", stdout);
#else
freopen("Supervision.in", "r", stdin);
freopen("Supervision.out", "w", stdout);
#endif
Initialize();
n = read<int>(), d = read<int>();
for (int i = 1; i <= n; ++i) {
place[i] = read<int>(), indentity[i] = read<int>();
couchCount += indentity[i];
}
if (d == 0) {
printf("%lld\n", (pow2[couchCount] - 1 + MOD) % MOD);
return 0;
}
for (int mask = 0; mask < 1 << n; ++mask) {
std::vector<int> choose(1, 0);
for (int i = 1; i <= n; ++i) if ((mask >> (i - 1)) & 1) choose.push_back(i);
bool ok = true;
for (int i = 1; i < (int) choose.size(); ++i) {
if (indentity[choose[i]]) continue;
for (int j = i - 1; j >= 1 && place[choose[i]] - place[choose[j]] >= d; --j) if (indentity[choose[j]]) continue;
ok = false;
break;
}
if (ok) if (++ans == MOD) ans = 0;
}
printf("%lld\n", ans);
return 0;
}