QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#752709#5983. Pretty Good ProportionPengAo0 2551ms15832kbC++141.4kb2024-11-16 09:23:052024-11-16 09:23:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 09:23:08]
  • 评测
  • 测评结果:0
  • 用时:2551ms
  • 内存:15832kb
  • [2024-11-16 09:23:05]
  • 提交

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'