QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#803207 | #9081. Stone Game | pengpeng_fudan# | AC ✓ | 56ms | 5604kb | C++23 | 1.3kb | 2024-12-07 16:25:14 | 2024-12-07 16:25:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
void solve(int T){
auto print=[&](string ans)->void {
cout<<"Case "<<T<<": "<<ans<<'\n';
return ;
};
int n;
cin>>n;
vector<int> nim(n+2);
nim[0]=nim[n+1]=2000000000;
for(int i=1;i<=n;i++){
cin>>nim[i];
}
for(int i=1;i<=n;i++){
if(nim[i]==nim[i+1]||nim[i]==nim[i-1]){
print("Bob");
return ;
}
}
vector<int> ope;
vector<int> tag(n+2,-1);
for(int i=1;i<=n;i++){
if(nim[i]<nim[i+1]&&nim[i]<nim[i-1]){
ope.push_back(i);
}
}
for(auto i:ope){
int l=i-1,r=i+1;
tag[i]=0;
while(l>=1){
tag[l]=max(tag[l+1]+1,tag[l]);
if(nim[l-1]<nim[l]) break;
l--;
}
while(r<=n){
tag[r]=max(tag[r-1]+1,tag[r]);
if(nim[r+1]<nim[r]) break;
r++;
}
}
int sg=0;
for(int i=1;i<=n;i++){
sg+=(nim[i]-tag[i]);
// cerr<<tag[i]<<'\n';
assert(nim[i]>=tag[i]);
}
if(sg%2==0) print("Bob");
else print("Alice");
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
int _ = 1;
cin >> _;
int tot=0;
while (_--) solve(++tot);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
2 2 1 3 3 1 3 1
output:
Case 1: Alice Case 2: Bob
result:
ok 6 tokens
Test #2:
score: 0
Accepted
time: 56ms
memory: 5604kb
input:
100 6 81465064 282461216 901271977 883929195 417402583 905199019 81 446515977 713783802 722110667 630976811 649946782 587154674 902746167 323984832 993767142 448219489 147260653 965726731 285094827 38139235 232364598 865618962 179012832 170557710 51496918 387305162 297154531 40736146 181070561 68158...
output:
Case 1: Alice Case 2: Alice Case 3: Alice Case 4: Alice Case 5: Alice Case 6: Alice Case 7: Bob Case 8: Alice Case 9: Alice Case 10: Alice Case 11: Bob Case 12: Bob Case 13: Bob Case 14: Alice Case 15: Bob Case 16: Bob Case 17: Alice Case 18: Alice Case 19: Alice Case 20: Bob Case 21: Alice Case 22:...
result:
ok 300 tokens
Extra Test:
score: 0
Extra Test Passed