답안 #656356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656356	2022-11-07T03:58:11 Z	perchuts	Lottery (CEOI18_lot)	C++17	100 / 100	486 ms	8252 KB

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e4+1;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int a[maxn], where[maxn], ans[maxn][101], resp[100];

int main(){_
    int n,l;cin>>n>>l;

    for(int i=1;i<=n;++i)cin>>a[i];    

    int q;cin>>q;

    vector<int>qu(q), ord;

    for(int i=0;i<q;++i)cin>>qu[i], ord.pb(qu[i]);

    sort(all(ord));

    ord.erase(unique(all(ord)),end(ord));

    int i = 0;

    for(int j=0;j<sz(ord);++j)
        while(i!=ord[j])++i, where[i] = j;
    
    while(i!=l)++i, where[i] = q;

    for(int i=1;i<=n-l;++i){//distance from two strings
        int x = 1, y = 1 + i, cur = 0;
        for(int j=0;j<l;++j)cur += (a[j+1]!=a[i+j+1]);
        ans[x++][where[cur]]++, ans[y++][where[cur]]++;
        while(y+l-1<=n){
            cur += (a[x+l-1]!=a[y+l-1])-(a[x-1]!=a[y-1]);
            ans[x++][where[cur]]++, ans[y++][where[cur]]++;
        }
    }

    for(int i=1;i<=n-l+1;++i)
        for(int j=1;j<sz(ord);++j)
            ans[i][j] += ans[i][j-1];
    
    for(auto x:qu)
        for(int i=1;i<=n-l+1;++i)cout<<ans[i][where[x]]<<" \n"[i==n-l+1];
    
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	18 ms	1136 KB	Output is correct
14	Correct	10 ms	852 KB	Output is correct
15	Correct	10 ms	852 KB	Output is correct
16	Correct	16 ms	1052 KB	Output is correct
17	Correct	12 ms	980 KB	Output is correct
18	Correct	15 ms	1016 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	4308 KB	Output is correct
2	Correct	417 ms	4308 KB	Output is correct
3	Correct	414 ms	4308 KB	Output is correct
4	Correct	403 ms	4248 KB	Output is correct
5	Correct	121 ms	2360 KB	Output is correct
6	Correct	360 ms	4032 KB	Output is correct
7	Correct	122 ms	2344 KB	Output is correct
8	Correct	205 ms	3148 KB	Output is correct
9	Correct	393 ms	4188 KB	Output is correct
10	Correct	399 ms	4232 KB	Output is correct
11	Correct	18 ms	1108 KB	Output is correct
12	Correct	201 ms	3112 KB	Output is correct
13	Correct	162 ms	2704 KB	Output is correct
14	Correct	161 ms	2716 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	4308 KB	Output is correct
2	Correct	417 ms	4308 KB	Output is correct
3	Correct	414 ms	4308 KB	Output is correct
4	Correct	403 ms	4248 KB	Output is correct
5	Correct	121 ms	2360 KB	Output is correct
6	Correct	360 ms	4032 KB	Output is correct
7	Correct	122 ms	2344 KB	Output is correct
8	Correct	205 ms	3148 KB	Output is correct
9	Correct	393 ms	4188 KB	Output is correct
10	Correct	399 ms	4232 KB	Output is correct
11	Correct	18 ms	1108 KB	Output is correct
12	Correct	201 ms	3112 KB	Output is correct
13	Correct	162 ms	2704 KB	Output is correct
14	Correct	161 ms	2716 KB	Output is correct
15	Correct	384 ms	4188 KB	Output is correct
16	Correct	343 ms	3924 KB	Output is correct
17	Correct	407 ms	4304 KB	Output is correct
18	Correct	407 ms	4268 KB	Output is correct
19	Correct	409 ms	4268 KB	Output is correct
20	Correct	409 ms	4264 KB	Output is correct
21	Correct	409 ms	4264 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	18 ms	1136 KB	Output is correct
14	Correct	10 ms	852 KB	Output is correct
15	Correct	10 ms	852 KB	Output is correct
16	Correct	16 ms	1052 KB	Output is correct
17	Correct	12 ms	980 KB	Output is correct
18	Correct	15 ms	1016 KB	Output is correct
19	Correct	421 ms	4308 KB	Output is correct
20	Correct	417 ms	4308 KB	Output is correct
21	Correct	414 ms	4308 KB	Output is correct
22	Correct	403 ms	4248 KB	Output is correct
23	Correct	121 ms	2360 KB	Output is correct
24	Correct	360 ms	4032 KB	Output is correct
25	Correct	122 ms	2344 KB	Output is correct
26	Correct	205 ms	3148 KB	Output is correct
27	Correct	393 ms	4188 KB	Output is correct
28	Correct	399 ms	4232 KB	Output is correct
29	Correct	18 ms	1108 KB	Output is correct
30	Correct	201 ms	3112 KB	Output is correct
31	Correct	162 ms	2704 KB	Output is correct
32	Correct	161 ms	2716 KB	Output is correct
33	Correct	384 ms	4188 KB	Output is correct
34	Correct	343 ms	3924 KB	Output is correct
35	Correct	407 ms	4304 KB	Output is correct
36	Correct	407 ms	4268 KB	Output is correct
37	Correct	409 ms	4268 KB	Output is correct
38	Correct	409 ms	4264 KB	Output is correct
39	Correct	409 ms	4264 KB	Output is correct
40	Correct	423 ms	5076 KB	Output is correct
41	Correct	13 ms	852 KB	Output is correct
42	Correct	422 ms	5028 KB	Output is correct
43	Correct	388 ms	4528 KB	Output is correct
44	Correct	397 ms	4644 KB	Output is correct
45	Correct	486 ms	8104 KB	Output is correct
46	Correct	18 ms	1100 KB	Output is correct
47	Correct	478 ms	8252 KB	Output is correct
48	Correct	442 ms	6280 KB	Output is correct
49	Correct	444 ms	6940 KB	Output is correct

답안 #656356

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0