QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#840167 | #1102. Guard | RedDiamond# | 0 | 0ms | 3532kb | C++17 | 2.2kb | 2025-01-02 16:02:32 | 2025-01-02 16:02:33 |
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 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;
sort(a + 1, a + m + 1);
vector<int> b(n + 1, -1);
vector<int> rem;
for (int i = 1; i <= m; ++i) rem.push_back(i);
while (!rem.empty()) {
vector<int> nwrem;
for (auto i : rem) {
int l = a[i].l;
int r = a[i].r;
int t = a[i].t;
if (t == 0) {
for (int j = l; j <= r; ++j) b[j] = 0;
} else {
int cnt = 0;
for (int j = l; j <= r; ++j) cnt += b[j] == 0;
int ones = 0;
for (int j = l; j <= r; ++j) ones += b[j] == 1;
if (cnt == r - l && ones == 1) continue;
if (cnt == r - l && ones == 0) {
for (int j = l; j <= r; ++j) {
if (b[j] == -1) b[j] = 1;
}
--k;
} else {
nwrem.push_back(i);
}
}
}
if (nwrem.size() == rem.size()) break;
rem = nwrem;
}
if (k == 1) {
int l = 0, r = n + 1;
for (auto i : rem) if (a[i].t == 1) ckmax(l, a[i].l), ckmin(r, a[i].r);
int cnt = 0;
for (int i = l; i <= r; ++i) if (b[i] == -1) ++cnt;
if (cnt == 1) {
for (int i = l; i <= r; ++i) if (b[i] == -1) b[i] = 1;
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (b[i] == 1) cout << i << "\n", ++cnt;
}
if (cnt == 0) cout << -1 << "\n";
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 0ms
memory: 3532kb
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: 0
Wrong Answer
time: 0ms
memory: 3528kb
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
result:
wrong answer 1st lines differ - expected: '1', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%