QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #325263 | #8230. Submissions | ucup-team1134# | WA | 90ms | 3892kb | C++23 | 10.6kb | 2024-02-11 06:50:41 | 2024-02-11 06:50:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
int M;cin>>M;
vector<tuple<string,int,int,int>> inpfake(M);
vector<array<int,4>> inp(M);
vector<string> teamname;
for(int i=0;i<M;i++){
string a;
char b;
int c;
string d;
cin>>a>>b>>c>>d;
int bb=b-'A';
int dd;
if(d=="accepted") dd=1;
else dd=0;
inpfake[i]={a,bb,c,dd};
teamname.push_back(a);
}
sort(all(teamname));
teamname.erase(unique(all(teamname)),teamname.end());
int N=si(teamname);
vector<vector<vector<int>>> S(N,vector<vector<int>>(26));
for(int i=0;i<M;i++){
inp[i][0]=lower_bound(all(teamname),get<0>(inpfake[i]))-teamname.begin();
inp[i][1]=get<1>(inpfake[i]);
inp[i][2]=get<2>(inpfake[i]);
inp[i][3]=get<3>(inpfake[i]);
auto [a,b,c,d]=inp[i];
if(d) S[a][b].push_back(c);
else S[a][b].push_back(~c);
}
vector<array<int,3>> def(N);
for(int i=0;i<N;i++) def[i][2]=i;
int sanka=0;
for(int i=0;i<N;i++){
for(int j=0;j<26;j++){
int pena=0;
for(int x:S[i][j]){
if(x>=0){
def[i][0]++;
pena+=x;
def[i][1]+=pena;
break;
}else{
pena+=20;
}
}
}
if(def[i][0]) sanka++;
}
auto defso=def;
sort(all(defso),[](auto a,auto b){
if(a[0]==b[0]) return a[1]<b[1];
else return a[0]>b[0];
});
vector<int> CAN(N);
for(int k=-1;k<min(36,N);k++){
auto T=def;
if(k>=0){
int i=defso[k][2];
array<int,3> mi={T[i][0],-T[i][1],T[i][2]};
for(int j=0;j<26;j++){
auto sv=T[i];
{
int pena=0;
for(int x:S[i][j]){
if(x>=0){
T[i][0]--;
pena+=x;
T[i][1]-=pena;
break;
}else{
pena+=20;
}
}
}
{
int musi=0;
int pena=0;
for(int x:S[i][j]){
if(x>=0){
if(musi==0){
pena+=20;
musi=1;
}else{
T[i][0]++;
pena+=x;
T[i][1]+=pena;
break;
}
}else{
pena+=20;
}
}
chmin(mi,{T[i][0],-T[i][1],T[i][2]});
}
T[i]=sv;
}
T[i]={mi[0],-mi[1],mi[2]};
}
sort(all(T),[](auto a,auto b){
if(a[0]==b[0]) return a[1]<b[1];
else return a[0]>b[0];
});
int can=0;
for(auto x:T) if(x[0]) can++;
can=min((can+9)/10,35);
//cout<<can<<endl;
if(can==0) continue;
for(auto x:T){
if(x[0]){
if(mp(-x[0],x[1])<=mp(-T[can-1][0],T[can-1][1])) CAN[x[2]]=true;
}
}
}
pair<int,int> rev=mp(-1,-1);
{
auto T=def;
for(int k=0;k<N;k++){
int i=defso[k][2];
array<int,3> ma={T[i][0],-T[i][1],T[i][2]};
for(int j=0;j<26;j++){
if(si(S[i][j])==0) continue;
auto sv=T[i];
{
int pena=0;
for(int x:S[i][j]){
if(x>=0){
T[i][0]--;
pena+=x;
T[i][1]-=pena;
break;
}else{
pena+=20;
}
}
}
{
T[i][0]++;
int x=S[i][j][0];
if(x>=0){
T[i][1]+=x;
}else{
T[i][1]+=~x;
}
}
chmax(ma,{T[i][0],-T[i][1],T[i][2]});
T[i]=sv;
}
int can;
if(T[i][0]==0&&ma[0]==1){
can=min((sanka+1+9)/10,35);
}else{
can=min((sanka+9)/10,35);
}
if(can==0) continue;
//cout<<can<<endl;
//cout<<ma[0]<<" "<<ma[1]<<" "<<ma[2]<<endl;
if(mp(-ma[0],-ma[1])<=mp(-T[can-1][0],T[can-1][1])) CAN[ma[2]]=true;
}
}
{
auto T=def;
for(int k=0;k<N;k++){
int i=defso[k][2];
auto ma=T[i];
if(ma[0]) continue;
for(int j=0;j<26;j++){
if(si(S[i][j])==0) continue;
auto sv=T[i];
{
int pena=0;
for(int x:S[i][j]){
if(x>=0){
T[i][0]--;
pena+=x;
T[i][1]-=pena;
break;
}else{
pena+=20;
}
}
}
{
T[i][0]++;
int x=S[i][j].back();
if(x>=0){
T[i][1]+=x;
}else{
T[i][1]+=~x;
}
T[i][1]+=20*(si(S[i][j])-1);
}
chmax(ma,T[i]);
T[i]=sv;
}
int can;
if(T[i][0]==0&&ma[0]==1){
can=min((sanka+1+9)/10,35);
chmax(rev,mp(ma[1],k));
}else{
can=min((sanka+9)/10,35);
}
if(can==0) continue;
if(mp(-ma[0],ma[1])<=mp(-T[can-1][0],T[can-1][1])) CAN[ma[2]]=true;
}
}
//cout<<rev.fi<<" "<<rev.se<<endl;
if(rev.fi!=-1){
int k=rev.se;
auto T=def;
int i=defso[k][2];
auto ma=T[i];
if(ma[0]) continue;
for(int j=0;j<26;j++){
if(si(S[i][j])==0) continue;
auto sv=T[i];
{
int pena=0;
for(int x:S[i][j]){
if(x>=0){
T[i][0]--;
pena+=x;
T[i][1]-=pena;
break;
}else{
pena+=20;
}
}
}
{
T[i][0]++;
int x=S[i][j].back();
if(x>=0){
T[i][1]+=x;
}else{
T[i][1]+=~x;
}
T[i][1]+=20*(si(S[i][j])-1);
}
chmax(ma,T[i]);
T[i]=sv;
}
T[i]=ma;
int can;
can=min((sanka+1+9)/10,35);
sort(all(T),[](auto a,auto b){
if(a[0]==b[0]) return a[1]<b[1];
else return a[0]>b[0];
});
if(can==0) continue;
for(auto x:T){
if(x[0]){
if(mp(-x[0],x[1])<=mp(-T[can-1][0],T[can-1][1])) CAN[x[2]]=true;
}
}
}
vector<string> res;
for(int i=0;i<N;i++) if(CAN[i]) res.push_back(teamname[i]);
cout<<si(res)<<"\n";
for(int i=0;i<si(res);i++){
if(i) cout<<" ";
cout<<res[i];
}
cout<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3892kb
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: 3724kb
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: 3628kb
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: 3864kb
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: 90ms
memory: 3688kb
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: 71ms
memory: 3768kb
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:
25 6RmtGgHJ 6SgZMn 6YPf7GECCSK 9XtB_VIfbRRL Bzs0PiQMXGZ5rRZ_2D FVJL FjP7vHdRibt H7Eb0AZyC9qWoY MyCqVEg1ONjZ Qua1Pti3vKhyQKDUm QxCmRRj3nOVKK Ra3Qeta_qR a c ex5qMuW fYuK1KNkuyO5HRCq hQ i29 im7tqW2RfLeuQ l5ClvOhvY_DEMrXu tXWpYVqjhksFCY tsd xiLm0TUOF3T xx2yiu6x zPqu 3 2RCjH1RBsfs91BQS3 JP t3 2 77sgqpbTI...
result:
wrong answer the numbers are different in the case 1. (test case 1)