QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #454844 | #8230. Submissions | ZSH_ZSH | RE | 0ms | 3992kb | C++14 | 4.2kb | 2024-06-25 15:23:06 | 2024-06-25 15:23:06 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define drep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
#define fir first
#define sec second
typedef pair<int,int> pii;
inline pii operator + (const pii &x,const pii &y){return {x.fir+y.fir,x.sec+y.sec};}
inline pii operator - (const pii &x,const pii &y){return {x.fir-y.fir,x.sec-y.sec};}
struct sub
{
int id,prob,t,status;
};
inline pii better(const pii &x,const pii &y)
{
if (x.fir<y.fir) return y;
if (x.fir>y.fir) return x;
return {x.fir,min(x.sec,y.sec)};
}
void solve()
{
int m; cin>>m;
int n=0;
map<string,int> teamid;
vector<string> names;
vector<array<vector<sub>,26> > V;
rep(i,1,m)
{
string name;
char prob;
int t;
string status;
cin>>name>>prob>>t>>status;
if (!teamid.count(name))
{
teamid[name]=n++;
V.push_back({});
names.push_back(name);
}
int id=teamid[name];
int p=prob-'A';
int s=(status[0]=='a')?1:0;
V[id][p].push_back((sub){id,p,t,s});
}
assert(V.size()==n);
auto getord=[&](const vector<pii> &score)
{
vector<int> ord(n);
rep(i,0,n-1) ord[i]=i;
sort(ord.begin(),ord.end(),[&](auto i,auto j)
{
auto x=score[i];
auto y=score[j];
if (better(x,y)!=y) return 1;
return 0;
});
return ord;
};
auto sim=[&](const vector<sub> &v) -> pii
{
pii now={0,0};
int wa=0;
for (auto it:v)
{
if (it.status==1)
{
return {1,it.t+wa*20};
}
else wa++;
}
return now;
};
vector<int> canwin(n);
auto simulate=[&]()
{
vector<pii> score(n);
rep(id,0,n-1)
{
rep(p,0,25)
{
score[id]=score[id]+sim(V[id][p]);
}
}
int valid=0;
rep(i,0,n-1) if (score[i].fir) valid++;
vector<int> ord=getord(score);
if (valid!=0)
{
int gold=min(35,(valid+9)/10);
rep(i,0,gold-1) canwin[ord[i]]=1;
int j=gold-1;
while (j+1<n&&score[ord[gold-1]]==score[ord[j+1]]) j++;
rep(i,gold,j) canwin[ord[i]]=1;
}
else rep(i,0,n-1) canwin[i]=1;
return score;
};
auto score=simulate();
auto ord=getord(score);
rep(ii,0,min(n-1,35))
{
int id=ord[ii];
pii best={0,0};
pii pos={-1,-1};
rep(p,0,25)
{
int f=-1;
rep(i,0,(int)V[id][p].size()-1) if (V[id][p][i].status==1)
{
f=i;
break;
}
if (f==-1) continue;
auto now=sim(V[id][p]);
V[id][p][f].status=0;
auto nxt=sim(V[id][p]);
V[id][p][f].status=1;
auto diff=now-nxt;
if (diff==better(best,diff))
{
pos={p,f};
best=diff;
}
}
if (pos.fir!=-1)
{
V[id][pos.fir][pos.sec].status=0;
simulate();
V[id][pos.fir][pos.sec].status=1;
}
}
int valid=0;
rep(i,0,n-1) if (score[i].fir) valid++;
int luckyt=-1;
array<int,3> lucky={-1,-1,-1};
rep(id,0,n-1)
{
pii best={0,0};
rep(p,0,25)
{
int f=-1;
rep(i,0,(int)V[id][p].size()-1) if (V[id][p][i].status==0)
{
f=i;
break;
}
if (f==-1) continue;
auto now=sim(V[id][p]);
V[id][p][f].status=1;
auto nxt=sim(V[id][p]);
V[id][p][f].status=0;
auto diff=nxt-now;
if (diff==better(best,diff))
{
best=diff;
}
}
auto ns=score[id]+best;
int nv=(valid-(score[id].fir>0)+(ns.fir>0));
if (nv)
{
int gold=(nv+9)/10;
auto g=score[ord[gold-1]];
if (better(score[ord[gold-1]],ns)==ns)
{
canwin[id]=1;
}
}
if (score[id].fir==0&&ns.fir!=0)
{
int t=0;
pii pos={-1,-1};
rep(p,0,25)
{
int f=-1;
rep(i,0,(int)V[id][p].size()-1) if (V[id][p][i].status==0)
{
if (t<V[id][p][i].t)
{
t=V[id][p][i].t;
pos={p,i};
}
}
}
if (t>luckyt)
{
luckyt=t;
lucky={id,pos.fir,pos.sec};
}
}
}
if (lucky[0]!=-1)
{
assert(score[lucky[0]].fir==0);
V[lucky[0]][lucky[1]][lucky[2]].status=1;
simulate();
V[lucky[0]][lucky[1]][lucky[2]].status=0;
}
vector<string> winner;
rep(i,0,n-1) if (canwin[i]) winner.push_back(names[i]);
printf("%d\n",winner.size());
for (auto x:winner) printf("%s ",x.c_str());
printf("\n");
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T; cin>>T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
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 TSxingxing10 TS1 4 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3992kb
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_fan jiangly 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
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 K B C D E F G H I J 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
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: -100
Runtime Error
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...