QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485715#8230. SubmissionsSwarthmoreWA 91ms3904kbC++206.1kb2024-07-21 02:23:482024-07-21 02:23:48

Judging History

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

  • [2024-07-21 02:23:48]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:3904kb
  • [2024-07-21 02:23:48]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const char nl = '\n';

// Increase:
// - Change problem to earliest success (could increase n)
// - Make another decrease rank (precompute)
// - Increase n (# that solve > 0 problems (everyone has at least 1 attempt))
//   - Should increase lowest one
//   - If currently have 0, could increase n simultaneously

// Decrease:
// - Change problem from earliest success to fail
//   - This either decreases total (could decrease n)
//   - Or increases penalty

struct Score {
	int score, penalty;
	bool operator<(const Score& o) const {
		if (score != o.score) return score > o.score;
		return penalty < o.penalty;
	}
};
Score operator+(Score a, Score b) {
	return {a.score + b.score, a.penalty + b.penalty};
}

void solve() {
	int M; cin >> M;
	map<string, map<string, vector<pair<int, bool>>>> mp;
	while (M--) {
		string team; cin >> team;
		string prob; cin >> prob;
		int t; cin >> t;
    string s; cin >> s;
		bool p = s == "accepted";

		mp[team][prob].push_back({t, p});
	}

	int n = 0;
	vector<pair<Score, string>> scores;
	map<string, Score> toScore;
  vector<pair<Score, string>> newZeroScores;
	for (const auto& [team, m]: mp) {
		int num = 0;
		int penalty = 0;
		for (auto [_, v]: m) {
			bool got = false;
			int add = 0;
			int num_fail = 0;
			for (auto [t, s]: v) {
				if (s) {
					got = true;
					add += t;
					add += 20 * num_fail;
					break;
				}
				else {
					num_fail++;
				}
			}
			if (got) {
				num++;
				penalty += add;
			}
		}
		if (num > 0) n++;
		scores.push_back({{num, penalty}, team});
		toScore[team] = {num, penalty};
		// cout << team << ": " << num << ' ' << penalty << endl;
    
    // if have zero, add to zero scores
    if (num == 0) {
      int maxPenalty = 0;
      for (auto [_, v]: m) {
        maxPenalty = max(maxPenalty, v.back().first + 20 * (sz(v) - 1));
      }
      newZeroScores.push_back({{1, maxPenalty}, team});
    }
	}
	sort(all(scores));
  sort(all(newZeroScores));

  map<string, int> teamToIndex;
  for (int i = 0; i < sz(scores); i++) {
    teamToIndex[scores[i].second] = i;
  }

  vector<Score> justScores;
  for (auto [s, _]: scores) justScores.push_back(s);
	auto getr = [&](Score s) -> int {
		auto it = std::lower_bound(all(justScores), s);
		return distance(justScores.begin(), it);
	};

	int target = min((n + 9) / 10, 35);
	int new_target = min((n + 1 + 9) / 10, 35);
	int new_target_sub = min((n - 1 + 9) / 10, 35);

  // cout << target << ' ' << new_target << ' ' << new_target_sub << nl;

  vector<int> pfx(sz(scores) + 1);
  // get decrease scores
  for (int i = 0; i < sz(scores); i++) {
    auto [score, team] = scores[i];
    auto [num, penalty] = score;
		for (auto [_, v]: mp[team]) {
			int num_fail = 0;

      vector<int> accepts;
			for (auto [t, s]: v) {
				if (s) {
          accepts.push_back(t + 20 * num_fail);
          num_fail++;
          // don't break
				}
				else {
					num_fail++;
				}
			}

      int newScore = num, newPenalty = penalty;
			if (sz(accepts) > 0) {
        if (sz(accepts) == 1) {
          newScore--;
          newPenalty -= accepts[0];
        }
        else {
          // take next accept instead
          newPenalty = penalty - accepts[0] + accepts[1];
        }

        // only consider if doesn't decrease target
        if (newScore > 0 || new_target_sub == target) {
          // cout << "consider: " << team << ' ' << newScore << ' ' << newPenalty << endl;
          int ii = distance(justScores.begin(), upper_bound(all(justScores), score));
          int j = getr({newScore, newPenalty});
          // [ii, j)
          if (ii < j) {
            pfx[ii]++;
            pfx[j]--;
          }
        }
			}
		}
  }

  FOR(i, 1, sz(pfx)) {
    pfx[i] += pfx[i-1];
  }

	// cout << "target: " << target << ' ' << n << nl;

	map<string, int> canWin;

	for (const auto& [team, m]: mp) {
    auto [score, penalty] = toScore[team];
		canWin[team] = getr(toScore[team]) < target;
		for (auto [_, v]: m) {
			bool got = false;
			int add = 0;
			int num_fail = 0;
			for (auto [t, s]: v) {
				if (s) {
					got = true;
					add += t;
					add += 20 * num_fail;
					break;
				}
				else {
					num_fail++;
				}
			}
      int newScore = score, newPenalty = penalty;
      if (got) {
        newPenalty = penalty - add + v[0].first;
      }
      else {
        newScore++;
        newPenalty += v[0].first;
      }
      if (score == 0 && newScore > 0) {
        canWin[team] |= getr({newScore, newPenalty}) < new_target;
      }
      else {
        canWin[team] |= getr({newScore, newPenalty}) < target;
      }
		}

    // increase somebody else from 0
    for (int i = max(0, sz(newZeroScores) - 2); i < sz(newZeroScores); i++) {
      auto [zScore, zTeam] = newZeroScores[i];
      if (team != zTeam && !(zScore < toScore[team])) {
      // if (team != zTeam && toScore[team] < zScore) {
        canWin[team] |= getr({score, penalty}) < new_target;
      }
    }

    // check if we can decreasing other rank
    if (pfx[teamToIndex[team]] > 0) {
      canWin[team] |= getr(toScore[team]) - 1 < target;
    }
	}

	vector<string> wins;
	for (auto [team, w]: canWin) {
		if (w) wins.push_back(team);
	}
	cout << sz(wins) << nl;
	for (auto s: wins) cout << s << ' ';
	cout << nl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	while (T--) solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

2
5
TSxingxing10 G 0 rejected
TSxingxing10 B 83 accepted
aoliaoligeiliao J 98 accepted
TS1 J 118 accepted
TS1 B 263 accepted
12
AllWayTheNorth A 0 rejected
YaoYaoLingXian Y 10 accepted
XuejunXinyoudui1 X 200 rejected
XuejunXinyoudui1 X 200 accepted
LetItRot L 215 accepted
AllWayTheNorth W 250 accept...

output:

2
TS1 TSxingxing10 
4
AllWayTheNorth ImYourFan LetItRot XuejunXinyoudui1 

result:

ok 2 test cases ok. (2 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

2
2
jiangly_fan A 1 accepted
jiangly B 23 accepted
3
conqueror_of_tourist A 1 accepted
conqueror_of_tourist A 2 accepted
tourist B 23 accepted

output:

2
jiangly jiangly_fan 
1
conqueror_of_tourist 

result:

ok 2 test cases ok. (2 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

2
13
A A 1 accepted
A X 1 accepted
K K 1 rejected
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
K K 2 rejected
12
A A 1 accepted
A X 1 accepted
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 a...

output:

11
A B C D E F G H I J K 
1
A 

result:

ok 2 test cases ok. (2 test cases)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2
11
A A 1 accepted
B B 1 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
K K 2 accepted
12
A A 1 accepted
A X 1 accepted
K K 1 rejected
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 a...

output:

2
A B 
2
A K 

result:

ok 2 test cases ok. (2 test cases)

Test #5:

score: 0
Accepted
time: 80ms
memory: 3904kb

input:

100000
1
M3JytWoaEXxkACy_mBAQ R 111 accepted
1
sQ O 151 accepted
1
JinbrcS58gNEE5yTSkT B 140 accepted
1
cklwBY V 243 accepted
1
v_o42YmvEKFwy Q 260 rejected
1
ftQVK8S_um22w K 265 accepted
1
_bQBeFeDpYQhvZcLf9l3 Z 147 accepted
1
KvDcEAIDN A 75 rejected
1
H3MUK6 A 101 rejected
1
gxYo_oCFn2J8aIben U 54...

output:

1
M3JytWoaEXxkACy_mBAQ 
1
sQ 
1
JinbrcS58gNEE5yTSkT 
1
cklwBY 
1
v_o42YmvEKFwy 
1
ftQVK8S_um22w 
1
_bQBeFeDpYQhvZcLf9l3 
1
KvDcEAIDN 
1
H3MUK6 
1
gxYo_oCFn2J8aIben 
1
_isnlUGK0ddI 
1
BERcVjyCp 
1
6In2do_50ylch 
1
f0r3SXc6brMjT 
1
7njYOapSwvogA 
1
x 
1
y1w3KvxylfxwprRBYw 
1
aGedzS 
1
iPo0GDhIF 
1
4Vf...

result:

ok 100000 test cases ok. (100000 test cases)

Test #6:

score: -100
Wrong Answer
time: 91ms
memory: 3628kb

input:

10000
42
Bzs0PiQMXGZ5rRZ_2D G 2 accepted
9XtB_VIfbRRL E 11 accepted
FVJL M 13 rejected
a S 19 accepted
tsd Z 20 rejected
MyCqVEg1ONjZ U 22 accepted
6SgZMn N 51 rejected
Qua1Pti3vKhyQKDUm P 54 accepted
i29 M 63 accepted
zPqu D 68 rejected
xx2yiu6x C 71 rejected
fYuK1KNkuyO5HRCq L 76 rejected
tXWpYVqj...

output:

4
Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq tsd xiLm0TUOF3T 
2
JP t3 
2
77sgqpbTIr_Zt1 fhYPGC8W82NwJTQL 
2
3BQ pVWDEz 
2
buCeoOotAkV8DaFD6 tg 
1
UkXQ3iaNJ 
2
ALTqPt7JUSLrl vwfw 
1
QTEzV6tp 
3
4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz wJlbqIU 
2
6mbCu5zA eiuF7a_ 
1
xy6QBr8ECi 
3
PezeyUurYoz7N1iGU _Yej1PrINtydmO...

result:

wrong answer the numbers are different in the case 845. (test case 845)