QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771861 | #5140. Frozen Scoreboard | StanleyEx | TL | 0ms | 3856kb | C++14 | 3.2kb | 2024-11-22 16:04:53 | 2024-11-22 16:04:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u32 = unsigned;
using PII = pair<int, int>;
using ld = long double;
constexpr int P = 998244353;
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++) {
int cnt, penalty; cin >> cnt >> penalty;
int fro = 0;
vector<string> s(m);
vector<int> wa(m), pny(m, -1), sub(m);
vector<int> frozen;
getline(cin, s[0]);
for(int i = 0; i < m; i++) {
getline(cin, s[i]);
char op = s[i][0];
if(op == '.') continue;
int j = 2, t1 = 0, t2 = 0;
for(j = 2; isdigit(s[i][j]); j++) {
t1 = t1 * 10 + s[i][j] - '0';
}
j++;
for(; j < s[i].size(); j++) {
t2 = t2 * 10 + s[i][j] - '0';
}
if(op == '+') {
cnt--;
penalty -= (t1 - 1) * 20 + t2;
}
if(op == '?') {
frozen.push_back(i);
++fro;
wa[i] = t2 - t1;
sub[i] = t1 - 1;
}
}
vector<int> ans;
// cerr << cnt << " " << penalty << " " << fro << "\n";
if(cnt < 0 || penalty < 0 || cnt > fro || ((cnt || penalty) && !fro)) {
cout << "No\n";
continue;
}
auto dfs = [&] (auto self, int u, vector<int> vt) -> void {
if(!ans.empty()) return;
// cerr << "*" << u << " " << vt.size() << "\n";
if(vt.size() == cnt) {
int dirt = 0, unknown = 0;
for(int i : vt) {
// cerr << i << "*" << "\n";
dirt += wa[i];
unknown += sub[i];
}
//if(dirt + 240 * cnt <= penalty && dirt + unknown * 20 + 299 * cnt >= penalty) {
if(dirt * 20 + 240 * cnt <= penalty && unknown * 20 + 299 * cnt >= penalty) {
ans.clear();
for(auto i : vt) {
// cerr << i << " " << wa[i] << " " << sub[i] << "\n";
ans.push_back(i);
}
}
// cerr << "\n" << dirt << " " << penalty << " " << cnt << "\n";
return;
}
if(u >= fro) return;
for(int i = u; i < fro; i++) {
vt.push_back(frozen[i]);
self(self, i + 1, vt);
vt.pop_back();
}
};
vector<int> vt;
dfs(dfs, 0, vt);
if(ans.empty() && fro) {
cout << "No\n";
continue;
}
cout << "Yes\n";
for(auto i : ans) {
pny[i] = 240;
penalty -= 240 + wa[i] * 20;
}
//cout << "penalty: " << penalty << "\n";
if(!ans.empty()) {
int index = 0;
while(penalty > 59) {
if(index == ans.size()) {
index = 0;
}
if(sub[ans[index]] > 0) {
wa[ans[index]]++;
sub[ans[index]]--;
penalty -= 20;
}
index++;
}
pny[ans[0]] += penalty;
}
/*
for(auto i : ans) {
if(!penalty) break;
while(sub[i] > 0 && penalty >= 20) {
wa[i]++;
sub[i]--;
penalty -= 20;
}
int ti = min(penalty, 59);
pny[i] += ti;
penalty -= ti;
}
*/
for(int i = 0; i < m; i++) {
if(s[i][0] != '?') cout << s[i] << "\n";
else {
if(pny[i] == -1) {
cout << "- " << wa[i] + sub[i] + 1 << "\n";
} else {
cout << "+ " << wa[i] + 1 << "/" << pny[i] << "\n";
}
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
1 13 7 951 + 1/6 ? 3 4 + 4/183 - 2 + 3/217 . . . + 2/29 + 1/91 . + 1/22 .
output:
Yes + 1/6 + 2/263 + 4/183 - 2 + 3/217 . . . + 2/29 + 1/91 . + 1/22 .
result:
ok ok (1 test case)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
6 2 1 100 . ? 3 4 2 100 + 1/1 + 1/2 0 0 - 5 - 6 2 480 ? 100 100 ? 100 100 2 480 ? 99 100 ? 100 100 1 2000 ? 100 100 ? 100 100
output:
No No Yes - 5 - 6 Yes + 1/240 + 1/240 No Yes + 87/280 - 100
result:
ok ok (6 test cases)
Test #3:
score: -100
Time Limit Exceeded
input:
1000 13 6 1519 + 3/183 - 1 + 9/133 ? 2 3 - 5 ? 1 3 - 5 ? 1 1 ? 1 3 - 5 + 1/165 - 6 ? 2 5 2 570 - 2 - 9 . - 1 - 7 - 6 + 4/179 - 2 ? 2 5 . - 2 ? 1 3 . 1 140 . - 2 . - 2 - 1 - 2 - 2 . . . . + 3/100 . 1 195 + 1/195 . . . . . . . . ? 1 1 . . . 0 0 . . . . . . . . . . . . . 3 776 ? 8 22 ? 1 8 - 6 + 1/173 ...