QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187825 | #5140. Frozen Scoreboard | LilyWhite | WA | 2ms | 3780kb | C++14 | 5.2kb | 2023-09-25 00:21:44 | 2023-09-25 00:21:45 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
#define repn(i, n) for (int i = 1; i <= (int)n; i++)
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repr(i, m, n) for (int i = (int)m; i <= (int)n; i++)
#define repd(i, m, n) for (int i = (int)m; i >= (int)n; i--)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#ifdef LILYWHITE
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) ;
#endif
const int __attribute__((unused)) INF = 0x3f3f3f3f;
template <typename T> inline T rd(T &x) {
x = 0;
T neg = 1;
char c = 0;
while (c < '0' || c > '9') {
if (c == '-')
neg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - 48;
c = getchar();
}
x *= neg;
return x;
}
template <typename T, typename... Args> inline void rd(T &x, Args &...args) {
rd(x);
rd(args...);
}
const int N = 1010;
const int M = 16;
int n, m;
int main() {
ios::sync_with_stdio(false);
rd(n, m);
rep(i, n) {
int finalScore, finalPenalty, knownScore = 0, knownPenalty = 0;
vector<pair<int, int>> attempts(m);
vector<pair<int, int>> status(m);
vector<int> pendingProblems;
int totalAttempted = 0;
rd(finalScore, finalPenalty);
rep(j, m) {
char probstatus = getchar();
switch (probstatus) {
case '+': {
int x, y;
scanf("%d/%d", &x, &y);
knownScore++;
knownPenalty += 20 * (x - 1) + y;
status[j] = make_pair(x, y);
break;
}
case '?': {
int x, y;
scanf("%d%d", &x, &y);
attempts[j] = make_pair(y - x, y);
// first => submissions made before board-freeze
// second => submissions made after board-freeze
totalAttempted++;
pendingProblems.push_back(j);
status[j] = make_pair(-3, -3);
break;
}
case '-': {
int x;
scanf("%d", &x);
status[j] = make_pair(-2, x);
break;
}
case '.':
status[j] = make_pair(-1, -1);
break;
default:
eprintf("Unknown type");
}
getchar();
eprintf("status => (%d, %d)\n", status[j].first, status[j].second);
}
finalPenalty -= knownPenalty;
finalScore -= knownScore;
eprintf("Final Result: %d %d\n", finalScore, finalPenalty);
bool foundSolution = false;
for (int mask = 0; mask < (1 << totalAttempted); mask++) {
int leastPenalty = 0, mostPenalty = 0;
bitset<M> passed;
int solved = 0;
for (int i = 0; i < totalAttempted; i++) {
if (mask & (1 << i)) {
leastPenalty += (attempts[pendingProblems[i]].first) * 20 + 240;
mostPenalty += (attempts[pendingProblems[i]].second - 1) * 20 + 299;
passed[pendingProblems[i]] = true;
solved++;
}
}
if (solved != finalScore) {
eprintf("Failed due to incorrect solve count");
continue;
}
eprintf("%d %d\n", leastPenalty, mostPenalty);
eprintf("### BEGIN ANSWER ###\n");
if (leastPenalty <= finalPenalty && finalPenalty <= mostPenalty) {
foundSolution = true;
int remainingPenalty = finalPenalty - leastPenalty;
puts("Yes");
for (int i = 0; i < m; i++) {
if (status[i].first == -1) {
puts(".");
} else if (status[i].first == -2) {
printf("- %d\n", status[i].second);
} else if (status[i].first > 0) {
printf("+ %d/%d\n", status[i].first, status[i].second);
} else {
if (passed[i]) {
eprintf("PASS\n");
// greedily try to use all remaining penalty time
int maxPossiblePenalty = 20 * (attempts[i].second - 1) + 299 - 240;
if (remainingPenalty > maxPossiblePenalty) {
remainingPenalty -= maxPossiblePenalty;
printf("+ %d/299\n", attempts[i].second);
} else {
if (remainingPenalty == 0) {
printf("+ %d/240\n", attempts[i].first + 1);
} else {
eprintf("remaining penalty: %d\n", remainingPenalty);
int allowedRejectedSubmissions = min(remainingPenalty / 20, attempts[i].second - attempts[i].first - 1);
int allowedPenaltyTime = remainingPenalty - (allowedRejectedSubmissions * 20);
if (allowedPenaltyTime + 240 > 299) {
allowedPenaltyTime = 299 - 240;
}
printf("+ %d/%d\n", allowedRejectedSubmissions + attempts[i].first + 1, allowedPenaltyTime + 240);
remainingPenalty -= allowedPenaltyTime + allowedRejectedSubmissions * 20;
}
}
} else {
printf("- %d\n", attempts[i].second);
}
}
}
eprintf("### END ANSWER ###\n");
break;
}
}
if (!foundSolution) {
puts("No");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
input:
1 13 7 951 + 1/6 ? 3 4 + 4/183 - 2 + 3/217 . . . + 2/29 + 1/91 . + 1/22 .
output:
Yes + 1/6 + 3/243 + 4/183 - 2 + 3/217 . . . + 2/29 + 1/91 . + 1/22 .
result:
ok ok (1 test case)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3744kb
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 + 89/240 - 100
result:
ok ok (6 test cases)
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3732kb
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 ...
output:
Yes + 3/183 - 1 + 9/133 + 3/278 - 5 + 3/240 - 5 + 1/240 - 3 - 5 + 1/165 - 6 - 5 Yes - 2 - 9 . - 1 - 7 - 6 + 4/179 - 2 + 5/251 . - 2 - 3 . Yes . - 2 . - 2 - 1 - 2 - 2 . . . . + 3/100 . Yes + 1/195 . . . . . . . . - 1 . . . Yes . . . . . . . . . . . . . Yes - 22 - 8 - 6 + 1/173 - 11 - 9 - 3 - 6 + 6/25...
result:
wrong answer wrong total time (test case 18)