QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #325006 | #8230. Submissions | ucup-team008# | WA | 87ms | 3860kb | C++17 | 10.0kb | 2024-02-11 02:58:07 | 2024-02-11 02:58:07 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
#include <vector>
using namespace std;
// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
template<class T>
bool updmin(T& a, T b) {
if(b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool updmax(T& a, T b) {
if(b > a) {
a = b;
return true;
}
return false;
}
typedef int64_t ll;
void rsolve() {
int nops;
cin >> nops;
// subs[team][pid] -> {time, was accepted}
unordered_map<string, vector<vector<array<int, 2>>>> subs;
while(nops--) {
string s;
char t;
int a;
string b;
cin >> s >> t >> a >> b;
if(!subs.count(s)) subs[s].resize(26);
subs[s][t - 'A'].push_back({a, b[0] == 'a'});
}
vector<pair<string, array<int, 2>>> teams;
int nsolved = 0;
vector<vector<int>> times(27);
int biggestzeropen = -1;
for(const auto& [k, v]: subs) {
int solve = 0;
int timep = 0;
for(const auto& w: v) {
int wrong = 0;
if(sz(w) == 0) continue;
for(auto [a, b]: w) {
if(b) {
solve++;
timep += a + 20 * wrong;
break;
}
else wrong++;
}
}
times[solve].pb(timep);
nsolved += solve > 0;
teams.eb(k, array<int, 2>({solve, timep}));
if(solve == 0) {
for(const auto& w: v) {
if(sz(w) == 0) continue;
updmax(biggestzeropen, w.back()[0] + 20 * (sz(w)-1));
}
}
}
for(auto& v: times) sort(all(v));
sort(all(teams), [&](const auto a, const auto b) -> bool {
if(a.s[0] != b.s[0]) return a.s[0] > b.s[0];
return a.s[1] < b.s[1];
});
vector<string> ret;
array<int, 2> best = {1 << 30, 1 << 30};
array<int, 2> bestnonzero = {1 << 30, 1 << 30};
vector<array<int, 2>> worst;
vector<array<int, 2>> worstnonzero;
int widx = 0;
// debug("total teams solving before", nsolved);
for(auto team: teams) {
// debug("solving", team.f, team.s);
while(widx < sz(worst) && teams[widx].s != team.s) {
array<int, 2> cand = worst[widx];
if(cand[0] < best[0] || (cand[0] == best[0] && cand[1] > best[1])) best = cand;
cand = worstnonzero[widx];
if(cand[0] < bestnonzero[0] || (cand[0] == bestnonzero[0] && cand[1] > bestnonzero[1])) bestnonzero = cand;
widx++;
}
// debug("best demotion down to", best);
const vector<vector<array<int, 2>>>& sv = subs[team.f];
int bestsolve = 0;
int bestpenalty = 0;
for(int i = 0; i < 26; i++) {
if(sz(sv[i]) == 0) continue;
int fsolve = 1;
int fpen = sv[i][0][0];
int rsolve = 0;
int rpen = 0;
int wrong = 0;
for(auto [tt, issolved]: sv[i]) {
if(issolved) {
rsolve = 1;
rpen = tt + 20 * wrong;
break;
}
else wrong++;
}
if(fsolve == rsolve && fpen == rpen) continue;
if(fsolve-rsolve > bestsolve || (fsolve-rsolve == bestsolve && fpen - rpen < bestpenalty)) {
bestsolve = fsolve - rsolve;
bestpenalty = fpen - rpen;
}
}
bool canwin = false;
// flip enemy submission
if(team.s[0] > best[0] || (team.s[0] == best[0] && team.s[1] <= best[1])) {
// REMEMBER EDGE CASE WHERE TEAM SOLVES ONE AND GETS BUMPED TO ZERO
int nnsolved = nsolved;
if(best[0] == 0) nnsolved--;
int thresh = min(35, (nnsolved + 9) / 10);
if(team.s[0] > 0 && (widx-1) < thresh) canwin = true;
}
if(team.s[0] > bestnonzero[0] || (team.s[0] == bestnonzero[0] && team.s[1] <= bestnonzero[1])) {
assert(bestnonzero[0] > 0);
// REMEMBER EDGE CASE WHERE TEAM SOLVES ONE AND GETS BUMPED TO ZERO
int nnsolved = nsolved;
int thresh = min(35, (nnsolved + 9) / 10);
if(team.s[0] > 0 && (widx-1) < thresh) canwin = true;
}
// flip enemy zero to one
if(team.s[0] > 0 && biggestzeropen >= 0) {
int fsolve = team.s[0];
int fpen = team.s[1];
int above = 0;
for(int i = fsolve+1; i <= 26; i++) above += sz(times[i]);
above += lb(all(times[fsolve]), fpen) - times[fsolve].begin();
if(biggestzeropen < fpen) above++;
int nnsolved = nsolved + 1;
int thresh = min(35, (nnsolved + 9) / 10);
if(above < thresh) canwin = true;
}
// flip our submission
// REMEMBER EDGE CASE WHERE TEAM SOLVES ZERO AND BUMPS SOLVE>=1 BY 1
if(team.s[0] + bestsolve) {
int fsolve = team.s[0] + bestsolve;
int fpen = team.s[1] + bestpenalty;
// debug(fsolve, fpen);
int above = 0;
for(int i = fsolve+1; i <= 26; i++) above += sz(times[i]);
above += lb(all(times[fsolve]), fpen) - times[fsolve].begin();
int nnsolved = nsolved;
if(fsolve == 1 && team.s[0] == 0) nnsolved++;
int thresh = min(35, (nnsolved + 9) / 10);
// debug(above, thresh);
if(above < thresh) canwin = true;
}
if(canwin) ret.pb(team.f);
// TODO update worst dropped score?
{
int worstsolve = 0;
int worstpenalty = 0;
for(int i = 0; i < 26; i++) {
if(sz(sv[i]) == 0) continue;
int rsolve = 0;
int rpen = 0;
int wrong = 0;
for(auto [tt, issolved]: sv[i]) {
if(issolved) {
rsolve = 1;
rpen = tt + 20 * wrong;
break;
}
else wrong++;
}
int wsolve = 0;
int wpen = 0;
wrong = 0;
bool skippedsolve = false;
for(auto [tt, issolved]: sv[i]) {
if(issolved) {
if(!skippedsolve) {
skippedsolve = true;
wrong++;
}
else {
wsolve = 1;
wpen = tt + 20 * wrong;
break;
}
}
else wrong++;
}
if(wsolve == rsolve && wpen == rpen) continue;
// debug(wsolve, rsolve, wpen, rpen);
if(wsolve-rsolve < worstsolve || (wsolve-rsolve == worstsolve && wpen - rpen > worstpenalty)) {
worstsolve = wsolve - rsolve;
worstpenalty = wpen - rpen;
}
// debug(worstsolve, worstpenalty);
}
worst.pb({team.s[0] + worstsolve, team.s[1] + worstpenalty});
}
{
int worstsolve = 0;
int worstpenalty = 0;
for(int i = 0; i < 26; i++) {
if(sz(sv[i]) == 0) continue;
int rsolve = 0;
int rpen = 0;
int wrong = 0;
for(auto [tt, issolved]: sv[i]) {
if(issolved) {
rsolve = 1;
rpen = tt + 20 * wrong;
break;
}
else wrong++;
}
int wsolve = 0;
int wpen = 0;
wrong = 0;
bool skippedsolve = false;
for(auto [tt, issolved]: sv[i]) {
if(issolved) {
if(!skippedsolve) {
skippedsolve = true;
wrong++;
}
else {
wsolve = 1;
wpen = tt + 20 * wrong;
break;
}
}
else wrong++;
}
if(wsolve == rsolve && wpen == rpen) continue;
// debug(wsolve, rsolve, wpen, rpen);
if(team.s[0] + wsolve-rsolve > 0 && (wsolve-rsolve < worstsolve || (wsolve-rsolve == worstsolve && wpen - rpen > worstpenalty))) {
worstsolve = wsolve - rsolve;
worstpenalty = wpen - rpen;
}
// debug(worstsolve, worstpenalty);
}
worstnonzero.pb({team.s[0] + worstsolve, team.s[1] + worstpenalty});
}
}
sort(all(ret));
cout << sz(ret) << "\n";
for(int i = 0; i < sz(ret); i++) cout << ret[i] << " \n"[i == sz(ret)-1];
}
void solve() {
int t;
cin >> t;
while(t--) rsolve();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
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: 3640kb
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: 3660kb
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: 3652kb
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: 87ms
memory: 3860kb
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 4Vf5RXaTmySkFcXgHLOh 1...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Wrong Answer
time: 60ms
memory: 3676kb
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 _Yej1PrINtydmOudwoO ldaKL...
result:
wrong answer the numbers are different in the case 3703. (test case 3703)