QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #603861 | #8230. Submissions | Godwang | WA | 96ms | 200840kb | C++20 | 13.9kb | 2024-10-01 20:20:23 | 2024-10-01 20:20:24 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include <list>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x) & (-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod; //% mod
a = (a * a) % mod; //% mod
n >>= 1;
}
return ans;
}
inline void write(__int128 x)
{
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
__int128 sqrt(__int128 m)
{
__int128 leftt = 0, rightt = ((__int128)1) << 51, ret = -1, mid;
while (leftt < rightt)
{
mid = (leftt + rightt) / 2;
if (mid * mid > m)
{
rightt = mid;
}
else
{
leftt = mid + 1;
ret = mid;
}
}
return ret;
}
const double eps = 1e-6;
int sgn(double x)
{
if (fabs(x) < eps)
{
return 0;
}
else
return x < 0 ? -1 : 1;
}
struct Point
{
double x, y;
Point()
{
}
Point(double x, double y) : x(x), y(y)
{
}
Point operator+(Point B)
{
return Point(x + B.x, y + B.y);
}
Point operator-(Point B)
{
return Point(x - B.x, y - B.y);
}
bool operator==(Point B)
{
return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
}
bool operator<(Point B)
{
return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
}
};
typedef Point Vector;
double Cross(Vector A, Vector B) // 叉积
{
return A.x * B.y - A.y * B.x;
}
double Distance(Point A, Point B)
{
return hypot(A.x - B.x, A.y - B.y);
}
int Convex_hull(Point *p, int n, Point *ch)
{
n = unique(p, p + n) - p;
sort(p, p + n);
int v = 0;
for (int i = 0; i < n; i++)
{
while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
{
v--;
}
ch[v++] = p[i];
}
int j = v;
for (int i = n - 2; i >= 0; i--)
{
while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
{
v--;
}
ch[v++] = p[i];
}
if (n > 1)
{
v--;
}
return v;
}
int kmp(string s, string p)
{
int ans = 0, lastt = -1;
int lenp = p.size();
vector<int> Next(lenp + 3, 0);
rep(i, 1, lenp - 1)
{
int j = Next[i];
while (j && p[j] != p[i])
{
j = Next[j];
}
if (p[j] == p[i])
{
Next[i + 1] = j + 1;
}
else
{
Next[i + 1] = 0;
}
}
int lens = s.size();
int j = 0;
rep(i, 0, lens - 1)
{
while (j && s[i] != p[j])
{
j = Next[j];
}
if (s[i] == p[j])
{
j++;
}
if (j == lenp)
{
ans++;
}
}
return ans;
}
int dir[4][2] =
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
// {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };
#define endl '\n' // 交互题请删除本行
const ll inf = 1000000000000000000ll;
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
return fastpow(x, mod1 - 2, mod1);
}
const int N = 2e5 + 10, M = 1e6 + 10;
///////////////////////////////////
int tt;
int n, m;
map<string, int> ma;
set<string> se;
struct node
{
string name;
int ac;
ll tim;
vector<pair<bool, ll>> v[30];
ll hasac[30];
} st[N];
int cnt;
int goldac = 0;
ll goldtim = 0;
///////////////////////////////////
bool cmp(node x, node y)
{
if (x.ac != y.ac)
{
return x.ac > y.ac;
}
return x.tim < y.tim;
}
///////////////////////////////////
void init()
{
cnt = 0;
ma.clear();
se.clear();
rep(i, 1, m)
{
st[i].name = "";
st[i].ac = 0;
st[i].tim = 0;
rep(j, 1, 26)
{
st[i].v[j].clear();
st[i].hasac[j] = 0;
}
}
}
///////////////////////////////////
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); // 交互题请删除本行
// freopen("ain.txt", "r", stdin);
// freopen("aout.txt", "w", stdout);
cin >> tt;
int temp = 0;
rep(t, 1, tt)
{
cin >> m;
//
if (temp == 42)
{
if (t == 603)
{
cout << m << endl;
}
}
if (temp == 0)
{
temp = m;
}
init();
rep(i, 1, m)
{
string s;
char c;
ll tim;
string ver;
cin >> s >> c >> tim >> ver;
//
// if (temp == 42)
// {
// if (t == 603)
// {
// cout << s << " " << c << " " << tim << " " << ver << " ";
// if(i%6==0)
// {
// cout<<endl;
// }
// }
// }
if (ma.count(s) == 0)
{
ma[s] = ++cnt;
}
int id = ma[s];
st[id].name = s;
int timu = c - 'A' + 1;
//
// cout<<tim<<endl;
if (ver[0] == 'a') // dui
{
//
// cout<<"ac"<<endl;
st[id].v[timu].pb({1, tim});
if (st[id].hasac[timu] == 1)
{
}
else
{
st[id].ac++;
st[id].tim -= st[id].hasac[timu] * 20;
st[id].tim += tim;
st[id].hasac[timu] = 1;
}
}
else
{
//
st[id].v[timu].pb({0, tim});
st[id].hasac[timu]--;
//
// cout<<st[id].hasac[timu]<<"wa"<<endl;
}
// exit(0);
}
// //
// exit(0);
sort(st + 1, st + cnt + 1, cmp);
int not0 = 0;
rep(i, 1, cnt)
{
if (st[i].ac > 0)
{
not0++;
}
}
int gold = min(35, (not0 + 9) / 10);
//
if (temp == 42)
{
if (t == 603)
{
cout << not0 << " " << cnt << endl;
}
}
// cout<<gold<<endl;
goldac = st[gold].ac;
goldtim = st[gold].tim;
//
// cout<<"gold "<<goldac<<" "<<goldtim<<endl;
int hasgold = cnt;
int tongfen = 0;
//
// rep(i,1,cnt)
// {
// cout<<st[i].name<<" "<<st[i].ac<<" "<<st[i].tim<<endl;
// }
//
rep(i, 1, cnt)
{
if (st[i].ac > goldac || (st[i].ac == goldac && st[i].tim <= goldtim))
{
if (st[i].ac == goldac && st[i].tim == goldtim)
{
tongfen++;
}
se.insert(st[i].name);
}
else
{
hasgold = min(hasgold, i - 1);
break;
}
}
int tishu = 0;
ll fashi = 0;
int silverac = st[hasgold + 1].ac;
ll silvertim = st[hasgold + 1].tim;
bool flagg = 0;
rep(i, hasgold + 1, cnt) // not gold
{
rep(j, 1, 26)
{
int siz = st[i].v[j].size();
if (siz) // zhishao jiaole
{
if (st[i].hasac[j] != 1) // meiguo
{
if (st[i].ac >= 1 || min(35, (not0 + 10) / 10) == gold) // bubian
{
tishu = st[i].ac + 1;
fashi = st[i].tim + st[i].v[j][0].second;
if (tishu > goldac || (tishu == goldac && fashi <= goldtim))
{
se.insert(st[i].name);
break;
}
continue;
}
ll fa = 0;
for (auto ii : st[i].v[j])
{
tishu = st[i].ac + 1;
fashi = st[i].tim + st[i].v[j][0].second + fa * 20;
if (tishu > silverac || tishu == silverac && fashi <= silvertim)
{
se.insert(st[i].name);
}
else if (tishu == silverac && fashi >= silvertim)
{
flagg = 1;
}
fa++;
}
}
else
{
tishu = st[i].ac;
fashi = st[i].tim;
ll cuo = 0;
ll shijian = 0;
for (auto ii : st[i].v[j])
{
if (ii.first == 1)
{
shijian = ii.second;
break;
}
cuo++;
}
fashi -= cuo * 20 + shijian;
fashi += st[i].v[j][0].second;
}
if (tishu > goldac || (tishu == goldac && fashi <= goldtim))
{
se.insert(st[i].name);
break;
}
}
}
}
//
// cout<<hasgold<<endl;
if (hasgold < cnt && tongfen == 1 && flagg == 0)
{
bool flag = 0;
rep(i, 1, hasgold)
{
rep(j, 1, 26)
{
if (st[i].hasac[j] == 1)
{
int fla = 1;
ll cuo = 0;
tishu = st[i].ac;
fashi = st[i].tim;
for (auto ii : st[i].v[j])
{
if (ii.first == 1)
{
if (fla == 1)
{
tishu = st[i].ac - 1;
fashi -= cuo * 20 + ii.second;
//
// cout<<ii.second<<" "<<fashi<<endl<<endl;
fla = 0;
}
else
{
fla = 1;
tishu = st[i].ac;
fashi += cuo * 20 + ii.second;
break;
}
}
cuo++;
}
if (fla == 0 && st[i].ac == 1 && gold > min(35, (not0 + 8) / 10))
{
if (temp == 42)
{
if (t == 178)
{
cout << "ok";
}
continue;
}
continue;
}
//
// cout<<fashi<<endl<<endl;
if (tishu < silverac || (tishu == silverac && fashi >= silvertim))
{
flagg = 1;
goto t1;
}
}
}
}
}
t1:
if (flagg)
{
rep(i, hasgold + 1, cnt)
{
if (st[i].ac == silverac && st[i].tim == silvertim)
{
se.insert(st[i].name);
}
}
}
if (temp == 42)
{
if (t == 178)
{
cout << se.size() << endl;
for (auto i : se)
{
cout << i << " ";
}
cout << endl;
}
continue;
}
cout << se.size() << endl;
for (auto i : se)
{
cout << i << " ";
}
cout << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 31ms
memory: 200528kb
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: 28ms
memory: 200544kb
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: 26ms
memory: 200468kb
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: 24ms
memory: 200756kb
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: 64ms
memory: 200692kb
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: 96ms
memory: 200840kb
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:
1 _5I_n 27 10 12
result:
wrong answer the numbers are different in the case 1. (test case 1)