QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727914 | #5983. Pretty Good Proportion | londono | 0 | 6487ms | 68888kb | C++14 | 2.3kb | 2024-11-09 14:07:34 | 2024-11-09 14:07:35 |
Judging History
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'