QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771861#5140. Frozen ScoreboardStanleyExTL 0ms3856kbC++143.2kb2024-11-22 16:04:532024-11-22 16:04:53

Judging History

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

  • [2024-11-22 16:04:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-22 16:04:53]
  • 提交

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
...

output:


result: