QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187825#5140. Frozen ScoreboardLilyWhiteWA 2ms3780kbC++145.2kb2023-09-25 00:21:442023-09-25 00:21:45

Judging History

你现在查看的是最新测评结果

  • [2023-09-25 00:21:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3780kb
  • [2023-09-25 00:21:44]
  • 提交

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;
}

详细

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)