QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727914#5983. Pretty Good Proportionlondono0 6487ms68888kbC++142.3kb2024-11-09 14:07:342024-11-09 14:07:35

Judging History

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

  • [2024-11-09 14:07:35]
  • 评测
  • 测评结果:0
  • 用时:6487ms
  • 内存:68888kb
  • [2024-11-09 14:07:34]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long

#define dec double

using namespace std;
const int MAXN = (int)5e5+5;
const dec eps = 1e-6;

int n; char a[MAXN]; dec p, pp;

int pre[MAXN];
dec calc(int l, int r) { return (dec)(pre[r]-pre[l-1])/(r-l+1); }

int l, r; dec now;
void upd(int nl, int nr) {
    dec tmp = calc(nl, nr);
    if (fabs(tmp-pp)<fabs(now-pp) || (fabs(tmp-pp)<fabs(now-pp)+eps&&nl<l)) {
        now=tmp;
        l = nl, r = nr;
    }
}

#define pdi pair<dec,int>

#define mk make_pair

set<pdi> s; map<dec,bool> vis, _;

int main() {
    // g++ tii.cpp -o tii.exe -std=c++14 -O2 -fno-ms-extensions "-Wl,--stack=1000000000" -DLOCAL; ./tii
    time_t stm = clock();

    #ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("ans.out", "w", stdout);
    #else
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #endif

    int T; cin >> T; while (T--) {
        cin >> n >> p >> (a+1);
        if (p > 1.0-eps || p < 0.5) {
            p = 1.0-p;
            for (int i = 1; i <= n; i++) {
                a[i] = '0' + ((a[i]-'0')^1);
            }
        }
        pp = p;
        p /= (p-1.0);

        for (int i = 1; i <= n; i++) {
            pre[i]=pre[i-1]+(a[i]=='1');
        }

        now = 2;
        s.clear(); vis = _;
        
        dec pre = 0;
        s.insert(mk(0, 1)); vis[0] = 1;
        for (int i = 1; i <= n; i++) {
            pre += (a[i]=='0'?p:1);

            // printf("->>>>>>>>>>>%d %.2lf\n", i, pre);
            
            auto it = s.upper_bound(mk(pre, i+1));
            // if (it != s.end()) printf("[%d] !%d\n", i, (*it).second);
            if (it != s.end()) upd((*it).second, i); //, puts("A");
            if (it != s.begin()) --it, upd((*it).second, i); //, puts("B");
            // if (it != s.end()) printf("[%d] ?%d\n", i, (*it).second);
            if (!vis[pre]) vis[pre] = 1, s.insert(mk(pre,i+1));

            // printf("LINE %d: \n", i);
            // for (auto it = s.begin(); it != s.end(); it++) {
                // printf("[%.2lf,%d]", (*it).first, (*it).second);
            // } puts("");
        }

        cout << l << '\n';
    }

    cerr << "Exec Time: " << (double)(clock()-stm)/CLOCKS_PER_SEC << "s" << endl;
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 3944kb

input:

100
10 0.827672
0010101011
4 0.932623
0100
1000 0.834002
011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...

output:

7
2
11
1
1
2
1
1
1
1
1
5
6
565
1
1
1
1
1
1
1
1
1
845
1
1
2
156
1
1
1
1
1
1
394
2
174
1
3
1
131
4
1
841
2
2
1
1
75
1
2
1
1
1
1
1
2
1
2
1
1
1
9
1
1
839
3
3
1
1
1
613
1
6
1
1
1
1
1
1
2
1
321
1
1
7
80
1
1
1
1
1
2
1
2
159
1
1
4
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 6487ms
memory: 68888kb

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:

7
1
1
3
1
1
1
1
1
1
1
1
1
1
1
4334
1
1
124
1
1
1
1
1
1
1
1
4
1
682
1
1
3
1
1
1
1
1
2
3
1
289
3
2
2
1
1
1
1
1
1
1
1
2
1
2
1
6
6
1
2
2
1
3
2
1
7
4
1
501
2
1
1
2
1
2
189
4
1
7
499839
1
1
2
1
1
1
499841
1
1
9
5
1
2
1
1
1
93
1
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'