QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644775#3428. Spam FiltercrimsonsunsetAC ✓952ms4156kbC++201.5kb2024-10-16 15:27:132024-10-16 15:27:15

Judging History

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

  • [2024-10-16 15:27:15]
  • 评测
  • 测评结果:AC
  • 用时:952ms
  • 内存:4156kb
  • [2024-10-16 15:27:13]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long long ll;
typedef long double ld;

bool check(int len1, int cnt1, int len2, int cnt2) {
    return cnt1 * len2 < cnt2 * len1;
}

void solve() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    int n = s.size();
    vector<int> p(n + 1);
    for (int i = 0; i < n; ++i) p[i + 1] = p[i] + s[i] - '0';
    vector<bool> ok(n + 1, 1);
    int ansind = 0, anslen = k, cnt = 0;
    for (int i = k; i <= n; ++i) {
        if (ok[i]) {
            for (int j = i; j <= n; j += i) ok[j] = 0;
            for (int s = 0; s + i <= n; ++s) {
                if (check(anslen, cnt, i, p[s + i] - p[s])) {
                    ansind = s;
                    anslen = i;
                    cnt = p[s + i] - p[s];
                }
            }
        }
    }
    cout << ansind + 1 << ' ' << anslen;
}

signed main() {
    int tc = 1;
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

5
1000100000

output:

1 5

result:

ok success rate = 2/5 (~0.400000)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

5
1111111111111101110111111110110111111110010101110000010000000000000100010101000000000101010000000110

output:

1 5

result:

ok success rate = 1/1 (~1.000000)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

20
1101101111110111101010011111001111010101110011001110110011101111111101111111111111111111111011111111

output:

70 20

result:

ok success rate = 1/1 (~1.000000)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

4
101110010100

output:

1 5

result:

ok success rate = 4/5 (~0.800000)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

4
101110010010

output:

1 5

result:

ok success rate = 4/5 (~0.800000)

Test #6:

score: 0
Accepted
time: 948ms
memory: 4108kb

input:

100
10000111111000101010100100000001001010001100110111100110110100100011111000001111001001010010001000111101101010101101010011101000001111000001001110011110000001001110100100000001000110100001101011001011001101000111101101011011111011101011011000110111010010101001111000101000011100010011000000100000...

output:

83971 100

result:

ok success rate = 17/25 (~0.680000)

Test #7:

score: 0
Accepted
time: 16ms
memory: 3716kb

input:

83
111011111011001100011001001111101111110111101110101111111111111111111111111111111111111111111100000000000000000000000000000000000100001000000000001101110011010110000000101101010101000110010110111111011111111011111111101110011101100111110100000100011110001000111011001101000101010000010010000000000...

output:

4144 88

result:

ok success rate = 83/88 (~0.943182)

Test #8:

score: 0
Accepted
time: 952ms
memory: 4156kb

input:

100
11110110111100000100110011001111111111100111111111111111100111111111111110110111001010111100111100001000001001000000000001111111111101111111111110000000000001100101100110000010010001000001100011000000000000001000000000001000000001100111111111101110101111111101011111110011010100011100001001100011...

output:

62033 129

result:

ok success rate = 125/129 (~0.968992)

Test #9:

score: 0
Accepted
time: 948ms
memory: 4116kb

input:

100
11111111111111101101111111111111111111111101100000000001000000000000001010001010001001100000000000000000000000000000000000000000000010000100000000010000000000111111111111111111111111001010111111111111111011111101011111000011111111010111000000000000000000010000000000000000000000100011001000010100...

output:

59424 103

result:

ok success rate = 100/103 (~0.970874)

Test #10:

score: 0
Accepted
time: 947ms
memory: 4148kb

input:

94
110000100010100000001101000000011000001000001000001110100000000000100010010110010101000000000000010000000000010100110111000000100010001010001011000110000000000000000000000000000000000000000011000010000110000101000000000000000010010000000000100001000100000100010110000100010011010000110011100000011...

output:

55082 98

result:

ok success rate = 47/49 (~0.959184)

Test #11:

score: 0
Accepted
time: 951ms
memory: 4124kb

input:

98
100100000000000100000011011111101111100011101111111000111011100010111101011101010111111111111110111111101111111111111111100000000001000000000010000000100000000000111111111111111110111101111111111110111111011101111110011110101011101011000010000000000000010000010010100000111111110111101111011111111...

output:

13883 98

result:

ok success rate = 47/49 (~0.959184)

Test #12:

score: 0
Accepted
time: 951ms
memory: 4096kb

input:

98
111111111111111000000101001111010000001001001100110000101000100000001000010111001111111111111110111111111111111101111111101111111111111111111111111111011111111111011111101110010011110011111111110111111000000100101000010011001000010101001101011100000011111111111111101101110001000001000000000000000...

output:

51563 113

result:

ok success rate = 107/113 (~0.946903)

Test #13:

score: 0
Accepted
time: 17ms
memory: 3644kb

input:

100
10011110010111111100111111110101110111111111110011111111111101111111111111101110111111111111111111111101111111111111111101111110000100101000000110010001000100000011100010111111101010111011111010111011110110000010100000000100000001000000001100010110110001111101111111111001111111000010110110011110...

output:

1838 104

result:

ok success rate = 97/104 (~0.932692)

Test #14:

score: 0
Accepted
time: 17ms
memory: 3616kb

input:

100
11111111111111101110111100000000000000000000000010000100000100000000000000000000000000000000001000000000001010001000101111011101111110100111101111100011011101111101111110111001111111110111011001000000000000000000000000000000100010100000100000110110100100001000001000000000000000000000000000000000...

output:

3254 117

result:

ok success rate = 8/9 (~0.888889)

Test #15:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

2
00000

output:

1 2

result:

ok success rate = 0/1 (~0.000000)

Test #16:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

2
1010101

output:

1 3

result:

ok success rate = 2/3 (~0.666667)

Test #17:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

20
000111000110000000111011100000001010001010010100111011101101001111111010111101000101001110010001100001011111111100110001011111001100001110101000011011000111011001011101011101100010010001000101100000100110010111110100001011100110000011000010001011111011111100101100100111111110001001100010111001010...

output:

489 27

result:

ok success rate = 7/9 (~0.777778)