QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#840220 | #1102. Guard | RedDiamond# | 10 | 22ms | 3848kb | C++17 | 1.6kb | 2025-01-02 16:23:48 | 2025-01-02 16:23:49 |
Judging History
answer
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 1e5+7;
struct Ninja {
int l, r, t;
};
bool operator < (Ninja a, Ninja b) { // mai vedem
return a.r - a.l <= b.r - b.l;
}
Ninja a[N];
int one[N], zero[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k, m; cin >> n >> k >> m;
for (int i = 1; i <= m; ++i) cin >> a[i].l >> a[i].r >> a[i].t;
for (int mask = 0; mask < (1 << n); ++mask) {
if (__builtin_popcount(mask) != k) continue;
vector<int> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
bool bit = !!(mask & (1 << (i - 1)));
pref[i] = pref[i - 1] + bit;
}
bool ok = 1;
for (int i = 1; i <= m; ++i) {
int cnt = pref[a[i].r] - pref[a[i].l - 1];
if (cnt == 0 && a[i].t == 1) ok = 0;
if (cnt != 0 && a[i].t == 0) ok = 0;
}
if (ok == 1) {
for (int i = 1; i <= n; ++i) {
if (mask & (1 << (i - 1))) {
++one[i];
} else {
++zero[i];
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (one[i] != 0 && zero[i] == 0) {
cout << i << "\n";
++cnt;
}
}
if (cnt == 0) cout << -1 << "\n";
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 22ms
memory: 3552kb
input:
20 9 100 1 9 1 11 12 1 3 19 1 10 20 1 6 10 1 3 4 1 7 9 1 10 20 1 3 4 1 1 4 1 2 17 1 1 16 1 11 17 1 2 4 1 9 16 1 1 11 1 2 19 1 4 9 1 7 13 1 1 4 1 2 11 1 17 19 1 5 20 1 3 19 1 4 9 1 9 16 1 2 19 1 10 18 1 3 19 1 3 11 1 11 19 1 10 19 1 19 20 1 16 20 1 1 11 1 1 8 1 3 4 1 2 16 1 11 19 1 17 20 1 4 5 1 3 4 ...
output:
-1
result:
ok single line: '-1'
Test #2:
score: 10
Accepted
time: 10ms
memory: 3492kb
input:
20 12 20 12 14 1 16 19 1 6 18 1 1 9 1 7 11 1 17 17 0 5 5 0 1 14 1 3 8 1 9 9 0 10 10 0 18 18 0 9 9 0 7 14 1 13 13 0 8 8 0 4 4 0 2 20 1 13 13 0 18 20 1
output:
1 2 3 6 7 11 12 14 15 16 19 20
result:
ok 12 lines
Test #3:
score: 10
Accepted
time: 8ms
memory: 3588kb
input:
20 6 100 14 18 1 17 19 1 3 16 1 17 19 1 15 18 1 16 18 1 18 20 1 3 15 1 4 15 1 15 15 1 14 15 1 7 20 1 2 3 1 15 20 1 14 14 1 15 19 1 1 16 1 2 16 1 3 19 1 18 20 1 16 16 1 2 14 1 3 18 1 2 13 1 16 16 1 2 10 1 4 16 1 11 19 1 6 19 1 2 16 1 4 17 1 14 15 1 18 19 1 19 20 1 1 13 1 2 8 1 15 17 1 2 14 1 2 5 1 17...
output:
3 14 15 16 18 19
result:
ok 6 lines
Test #4:
score: 10
Accepted
time: 9ms
memory: 3560kb
input:
20 6 100 7 15 1 8 8 1 1 3 1 4 11 1 18 19 1 14 19 1 13 15 1 10 19 1 10 16 1 7 11 1 4 13 1 2 16 1 1 8 1 2 19 1 7 7 0 1 14 1 1 12 1 15 20 1 2 8 1 16 20 1 2 9 1 15 19 1 6 12 1 9 19 1 1 12 1 2 15 1 8 14 1 1 15 1 15 20 1 5 18 1 5 5 0 7 7 0 13 15 1 14 19 1 2 9 1 2 20 1 8 15 1 5 18 1 12 18 1 10 19 1 1 8 1 7...
output:
8 9 14 16 19
result:
ok 5 lines
Test #5:
score: 10
Accepted
time: 14ms
memory: 3848kb
input:
20 7 100 17 18 1 4 4 1 2 7 1 10 18 1 1 16 1 3 17 1 1 18 1 1 18 1 7 8 1 3 6 1 8 18 1 4 6 1 7 8 1 7 9 1 2 4 1 8 19 1 11 17 1 3 16 1 8 19 1 3 7 1 12 13 0 3 5 1 5 19 1 1 9 1 1 1 1 3 9 1 8 20 1 4 5 1 2 3 1 7 16 1 8 20 1 3 5 1 13 19 1 1 8 1 3 17 1 18 19 1 11 18 1 17 19 1 4 9 1 6 16 1 2 19 1 9 9 0 8 20 1 4...
output:
1 2 4 6 8 11 18
result:
ok 7 lines
Test #6:
score: 10
Accepted
time: 9ms
memory: 3616kb
input:
20 6 100 7 16 1 2 12 1 20 20 1 6 9 1 9 12 1 3 15 1 2 9 1 13 19 1 2 18 1 13 20 1 1 11 1 7 17 1 2 16 1 9 9 0 8 12 1 18 20 1 2 20 1 10 10 0 5 13 1 9 9 0 3 10 1 6 13 1 3 18 1 16 19 1 1 18 1 14 16 1 9 16 1 13 15 1 3 11 1 6 15 1 10 15 1 4 7 1 1 4 1 5 13 1 1 11 1 9 19 1 8 19 1 7 20 1 10 17 1 5 19 1 12 18 1...
output:
2 11 15 18 20
result:
ok 5 lines
Test #7:
score: 10
Accepted
time: 20ms
memory: 3548kb
input:
20 8 100 5 18 1 14 20 1 18 18 1 1 13 1 17 20 1 13 19 1 3 8 1 7 17 1 11 13 1 10 13 1 11 16 1 3 16 1 8 13 1 10 14 1 10 13 1 2 16 1 1 13 1 2 8 1 15 19 1 6 20 1 9 9 0 10 17 1 14 14 1 1 4 1 14 16 1 13 17 1 3 10 1 18 19 1 10 19 1 5 19 1 3 19 1 17 18 1 19 20 1 12 18 1 4 16 1 18 19 1 4 16 1 13 19 1 1 19 1 1...
output:
1 4 13 14 18
result:
ok 5 lines
Test #8:
score: 10
Accepted
time: 3ms
memory: 3616kb
input:
20 1 2 1 9 0 11 20 0
output:
10
result:
ok single line: '10'
Test #9:
score: 10
Accepted
time: 4ms
memory: 3556kb
input:
20 20 1 7 12 1
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
result:
ok 20 lines
Test #10:
score: 10
Accepted
time: 0ms
memory: 3592kb
input:
1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3624kb
input:
1000 604 1000 375 674 1 514 875 1 728 728 0 10 10 0 251 251 0 55 55 0 482 852 1 387 387 0 263 263 0 234 234 0 688 736 1 305 817 1 428 451 1 546 546 0 30 706 1 286 286 0 276 276 0 301 376 1 359 920 1 760 760 0 110 110 0 148 659 1 221 270 1 947 947 0 399 399 0 427 665 1 176 257 1 650 939 1 296 838 1 2...
output:
-1
result:
wrong answer 1st lines differ - expected: '1', found: '-1'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%