답안 #383628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383628	2021-03-30T12:22:20 Z	rumen_m	Lottery (CEOI18_lot)	C++17	100 / 100	2021 ms	8508 KB

# include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int a[maxn];
int calc(int x, int y, int l)
{
    int sum = 0;
    int i;
    for(i=0;i<l;i++)
    {
        if(a[x+i]!=a[y+i])sum++;
    }
    return sum;
}
struct queries
{
    int idx;
    int p[maxn];
    int k;
};
queries q[105];
bool cmp(queries i, queries j)
{
    return i.k>j.k;
}int Q;
void add(int x, int v)
{
    int uk1 = 1;
    int uk2 = Q;
    if(q[uk1].k<v)return ;
    int mid;
    while(uk1<uk2)
    {
        mid=  (uk1+uk2+1)>>1;
        if(q[mid].k>=v)uk1 = mid;
        else
            uk2 = mid-1;
    }
    q[uk2].p[x]++;
}
int newnum[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,l;
    cin>>n>>l;
    int i,j;
    for(i=1;i<=n;i++)cin>>a[i];

    cin>>Q;
    for(i=1;i<=Q;i++){q[i].idx=i;cin>>q[i].k;}
    sort(q+1,q+Q+1,cmp);
    for(i=2;i<=n-l+1;i++)
    {
        int num = calc(1,i,l);
        add(1,num);
        add(i,num);
        int f = 1;
        int s = i;
     //   cout<<f<<" - "<<s<<" : "<<num<<endl;
        for(j=i+1;j<=n-l+1;j++)
        {
            if(a[f]!=a[s])num--;
            f++;
            s++;
            if(a[f+l-1]!=a[s+l-1])num++;
            add(f,num);
            add(s,num);
           // cout<<f<<" - "<<s<<" : "<<num<<endl;
        }
    }
    for(i=Q;i>0;i--)
    {
        for(j=1;j<=n;j++)
            q[i].p[j]+=q[i+1].p[j];
    }
    for(i=1;i<=Q;i++)
        newnum[q[i].idx] = i;
    for(i=1;i<=Q;i++)
    {
        j = newnum[i];

        for(int t=1;t<=n-l+1;t++)
            cout<<q[j].p[t]<<" ";
        cout<<'\n';
    }
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	1260 KB	Output is correct
3	Correct	2 ms	1260 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	876 KB	Output is correct
7	Correct	3 ms	876 KB	Output is correct
8	Correct	3 ms	1260 KB	Output is correct
9	Correct	3 ms	1260 KB	Output is correct
10	Correct	3 ms	1260 KB	Output is correct
11	Correct	3 ms	1260 KB	Output is correct
12	Correct	3 ms	1260 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	1260 KB	Output is correct
3	Correct	2 ms	1260 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	876 KB	Output is correct
7	Correct	3 ms	876 KB	Output is correct
8	Correct	3 ms	1260 KB	Output is correct
9	Correct	3 ms	1260 KB	Output is correct
10	Correct	3 ms	1260 KB	Output is correct
11	Correct	3 ms	1260 KB	Output is correct
12	Correct	3 ms	1260 KB	Output is correct
13	Correct	25 ms	748 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Correct	7 ms	1004 KB	Output is correct
16	Correct	15 ms	1388 KB	Output is correct
17	Correct	9 ms	1388 KB	Output is correct
18	Correct	9 ms	1388 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	413 ms	492 KB	Output is correct
2	Correct	586 ms	488 KB	Output is correct
3	Correct	194 ms	620 KB	Output is correct
4	Correct	138 ms	492 KB	Output is correct
5	Correct	58 ms	492 KB	Output is correct
6	Correct	129 ms	492 KB	Output is correct
7	Correct	90 ms	492 KB	Output is correct
8	Correct	111 ms	492 KB	Output is correct
9	Correct	136 ms	492 KB	Output is correct
10	Correct	138 ms	492 KB	Output is correct
11	Correct	15 ms	492 KB	Output is correct
12	Correct	94 ms	492 KB	Output is correct
13	Correct	76 ms	492 KB	Output is correct
14	Correct	90 ms	492 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	413 ms	492 KB	Output is correct
2	Correct	586 ms	488 KB	Output is correct
3	Correct	194 ms	620 KB	Output is correct
4	Correct	138 ms	492 KB	Output is correct
5	Correct	58 ms	492 KB	Output is correct
6	Correct	129 ms	492 KB	Output is correct
7	Correct	90 ms	492 KB	Output is correct
8	Correct	111 ms	492 KB	Output is correct
9	Correct	136 ms	492 KB	Output is correct
10	Correct	138 ms	492 KB	Output is correct
11	Correct	15 ms	492 KB	Output is correct
12	Correct	94 ms	492 KB	Output is correct
13	Correct	76 ms	492 KB	Output is correct
14	Correct	90 ms	492 KB	Output is correct
15	Correct	273 ms	488 KB	Output is correct
16	Correct	123 ms	492 KB	Output is correct
17	Correct	163 ms	492 KB	Output is correct
18	Correct	144 ms	620 KB	Output is correct
19	Correct	139 ms	492 KB	Output is correct
20	Correct	127 ms	492 KB	Output is correct
21	Correct	127 ms	620 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	1260 KB	Output is correct
3	Correct	2 ms	1260 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	876 KB	Output is correct
7	Correct	3 ms	876 KB	Output is correct
8	Correct	3 ms	1260 KB	Output is correct
9	Correct	3 ms	1260 KB	Output is correct
10	Correct	3 ms	1260 KB	Output is correct
11	Correct	3 ms	1260 KB	Output is correct
12	Correct	3 ms	1260 KB	Output is correct
13	Correct	25 ms	748 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Correct	7 ms	1004 KB	Output is correct
16	Correct	15 ms	1388 KB	Output is correct
17	Correct	9 ms	1388 KB	Output is correct
18	Correct	9 ms	1388 KB	Output is correct
19	Correct	413 ms	492 KB	Output is correct
20	Correct	586 ms	488 KB	Output is correct
21	Correct	194 ms	620 KB	Output is correct
22	Correct	138 ms	492 KB	Output is correct
23	Correct	58 ms	492 KB	Output is correct
24	Correct	129 ms	492 KB	Output is correct
25	Correct	90 ms	492 KB	Output is correct
26	Correct	111 ms	492 KB	Output is correct
27	Correct	136 ms	492 KB	Output is correct
28	Correct	138 ms	492 KB	Output is correct
29	Correct	15 ms	492 KB	Output is correct
30	Correct	94 ms	492 KB	Output is correct
31	Correct	76 ms	492 KB	Output is correct
32	Correct	90 ms	492 KB	Output is correct
33	Correct	273 ms	488 KB	Output is correct
34	Correct	123 ms	492 KB	Output is correct
35	Correct	163 ms	492 KB	Output is correct
36	Correct	144 ms	620 KB	Output is correct
37	Correct	139 ms	492 KB	Output is correct
38	Correct	127 ms	492 KB	Output is correct
39	Correct	127 ms	620 KB	Output is correct
40	Correct	1408 ms	2152 KB	Output is correct
41	Correct	12 ms	1388 KB	Output is correct
42	Correct	263 ms	2156 KB	Output is correct
43	Correct	143 ms	1772 KB	Output is correct
44	Correct	159 ms	1900 KB	Output is correct
45	Correct	2021 ms	8300 KB	Output is correct
46	Correct	26 ms	4844 KB	Output is correct
47	Correct	1271 ms	8508 KB	Output is correct
48	Correct	215 ms	6636 KB	Output is correct
49	Correct	218 ms	7276 KB	Output is correct

답안 #383628

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