QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#752709 | #5983. Pretty Good Proportion | PengAo | 0 | 2551ms | 15832kb | C++14 | 1.4kb | 2024-11-16 09:23:05 | 2024-11-16 09:23:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Frac{
ll p,q;
Frac()=default;
constexpr Frac(ll p,ll q=1):p(p),q(q){}
bool operator<(const Frac &other)const{
return p*other.q<other.p*q;
}
Frac operator*(const Frac &other)const{
return Frac(p*other.p,q*other.q);
}
Frac operator-(const Frac &other)const{
return Frac(p*other.q-other.p*q,q*other.q);
}
};
inline Frac abs(const Frac &x){
return Frac(abs(x.p),x.q);
}
char s[500010],t[10];
int a[500010],b[500010];
Frac v[500010];
int main(){
int q,n,pos;Frac ans;
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>q;
for(int cnt=1;cnt<=q;cnt++){
cin>>n>>t>>s+1;pos=1e9;ans=1;
const Frac f((t[0]-'0')*1000000
+(t[2]-'0')*100000+(t[3]-'0')*10000
+(t[4]-'0')*1000+(t[5]-'0')*100
+(t[6]-'0')*10+t[7]-'0',1000000);
for(int i=1;i<=n;i++)
a[i]=a[i-1]+s[i]-'0',v[i]=Frac(a[i])-f*i,b[i]=i;
sort(b,b+n+1,[&](int x,int y){return v[x]<v[y];});
for(int i=0;i<=n;i++){
for(int j=i+1;j<=min(i+100,n);j++){
const int l=min(b[i],b[j]),r=max(b[i],b[j]);
const Frac t=abs(Frac(a[r]-a[l],r-l)-f);
if(t<ans)ans=t,pos=l;
else if(!(ans<t))pos=min(pos,l);
}
}
cout<<"Case #"<<cnt<<": "<<pos<<'\n';
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 5752kb
input:
100 10 0.827672 0010101011 4 0.932623 0100 1000 0.834002 011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...
output:
Case #1: 6 Case #2: 1 Case #3: 10 Case #4: 1 Case #5: 2 Case #6: 1 Case #7: 1 Case #8: 4 Case #9: 2 Case #10: 1 Case #11: 2 Case #12: 4 Case #13: 5 Case #14: 564 Case #15: 1 Case #16: 1 Case #17: 2 Case #18: 1 Case #19: 1 Case #20: 1 Case #21: 1 Case #22: 1 Case #23: 1 Case #24: 844 Case #25: 1 Case...
result:
wrong answer 4th lines differ - expected: 'Case #4: 0', found: 'Case #4: 1'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 2551ms
memory: 15832kb
input:
100 15 0.333333 000000000011000 10 0.418754 0101100001 2 0.499999 01 3 0.977951 001 2 0.249999 01 10 0.670229 0111011001 1000 0.500001 001101111110110010110000010010110001110010001101110111010011000010100011011101010110011011011010111110011100011000001000101011100011010100101101111110100101011010111...
output:
Case #1: 6 Case #2: 0 Case #3: 0 Case #4: 2 Case #5: 0 Case #6: 0 Case #7: 0 Case #8: 6 Case #9: 2 Case #10: 1 Case #11: 1 Case #12: 1 Case #13: 1 Case #14: 1 Case #15: 1 Case #16: 4333 Case #17: 1 Case #18: 1 Case #19: 123 Case #20: 2 Case #21: 1 Case #22: 1 Case #23: 2 Case #24: 2 Case #25: 2 Case...
result:
wrong answer 8th lines differ - expected: 'Case #8: 0', found: 'Case #8: 6'