oj.uz

답안 #530864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530864 2022-02-27T02:57:30 Z ToroTN JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 9 ms 3264 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,l[200005],r[200005],ans=1e9,ll,rr;
char s[200005];
vector<int> v[3];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='J')
        {
            v[0].push_back(i);
        }else if(s[i]=='O')
        {
            v[1].push_back(i);
        }else
        {
            v[2].push_back(i);
        }
    }
    /*for(int i=0;i<3;i++)
    {
        printf("%d\n",i);
        for(int j=0;j<v[i].size();j++)
        {
            printf("%d ",v[i][j]);
        }
        printf("\n");
    }*/
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
    {
        printf("-1\n");
    }else
    {
        for(int i=m-1;i<v[0].size();i++)
        {
            if(i==v[0].size()-1)
            {
                for(int j=v[0][i];j<=n;j++)
                {
                    l[j]=v[0][i-m+1];
                }
            }else
            {
                for(int j=v[0][i];j<v[0][i+1];j++)
                {
                    l[j]=v[0][i-m+1];
                }
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("%d ",l[i]);
        }
        printf("\n");*/
        for(int i=v[2].size()-m;i>=0;i--)
        {
            //printf("%d\n",i);
            if(i==0)
            {
                for(int j=v[2][i];j>=1;j--)
                {
                    r[j]=v[2][i+m-1];
                }
            }else
            {
                for(int j=v[2][i];j>v[2][i-1];j--)
                {
                    r[j]=v[2][i+m-1];
                }
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("%d ",r[i]);
        }
        printf("\n");*/
        for(int i=m-1;i<v[1].size();i++)
        {
            ll=v[1][i-m+1];
            rr=v[1][i];
            //printf("%d %d %d %d\n",ll,rr,l[ll],r[rr]);
            if(l[ll]!=-1&&r[rr]!=-1)
            {
                ans=min(ans,r[rr]-l[ll]+1-3*m);
            }
        }
        if(ans==1e9)
        {
            printf("-1\n");
        }else
        {
            printf("%d\n",ans);
        }
    }
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:34:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |        ~~~~~~~~~~~^~
ho_t2.cpp:34:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |                       ~~~~~~~~~~~^~
ho_t2.cpp:34:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |                                      ~~~~~~~~~~~^~
ho_t2.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=m-1;i<v[0].size();i++)
      |                       ~^~~~~~~~~~~~
ho_t2.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(i==v[0].size()-1)
      |                ~^~~~~~~~~~~~~~~
ho_t2.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=m-1;i<v[1].size();i++)
      |                       ~^~~~~~~~~~~~
ho_t2.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
ho_t2.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%s",s+1);
      |     ~~~~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 1 ms 1840 KB Output is correct
4 Correct 1 ms 1840 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1836 KB Output is correct
7 Correct 2 ms 1844 KB Output is correct
8 Correct 2 ms 1836 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1740 KB Output is correct
13 Correct 1 ms 1740 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 1 ms 1840 KB Output is correct
4 Correct 1 ms 1840 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1836 KB Output is correct
7 Correct 2 ms 1844 KB Output is correct
8 Correct 2 ms 1836 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1740 KB Output is correct
13 Correct 1 ms 1740 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct
15 Correct 1 ms 1836 KB Output is correct
16 Correct 1 ms 1868 KB Output is correct
17 Correct 1 ms 1836 KB Output is correct
18 Correct 1 ms 1868 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 1 ms 1868 KB Output is correct
22 Correct 1 ms 1844 KB Output is correct
23 Correct 1 ms 1844 KB Output is correct
24 Correct 2 ms 1868 KB Output is correct
25 Correct 1 ms 1868 KB Output is correct
26 Correct 2 ms 1768 KB Output is correct
27 Correct 1 ms 1868 KB Output is correct
28 Correct 1 ms 1868 KB Output is correct
29 Correct 1 ms 1868 KB Output is correct
30 Correct 1 ms 1868 KB Output is correct
31 Correct 1 ms 1868 KB Output is correct
32 Correct 1 ms 1868 KB Output is correct
33 Correct 1 ms 1868 KB Output is correct
34 Correct 1 ms 1868 KB Output is correct
35 Correct 1 ms 1868 KB Output is correct

Subtask #3
87.0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 1 ms 1840 KB Output is correct
4 Correct 1 ms 1840 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1836 KB Output is correct
7 Correct 2 ms 1844 KB Output is correct
8 Correct 2 ms 1836 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1740 KB Output is correct
13 Correct 1 ms 1740 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct
15 Correct 1 ms 1836 KB Output is correct
16 Correct 1 ms 1868 KB Output is correct
17 Correct 1 ms 1836 KB Output is correct
18 Correct 1 ms 1868 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 1 ms 1868 KB Output is correct
22 Correct 1 ms 1844 KB Output is correct
23 Correct 1 ms 1844 KB Output is correct
24 Correct 2 ms 1868 KB Output is correct
25 Correct 1 ms 1868 KB Output is correct
26 Correct 2 ms 1768 KB Output is correct
27 Correct 1 ms 1868 KB Output is correct
28 Correct 1 ms 1868 KB Output is correct
29 Correct 1 ms 1868 KB Output is correct
30 Correct 1 ms 1868 KB Output is correct
31 Correct 1 ms 1868 KB Output is correct
32 Correct 1 ms 1868 KB Output is correct
33 Correct 1 ms 1868 KB Output is correct
34 Correct 1 ms 1868 KB Output is correct
35 Correct 1 ms 1868 KB Output is correct
36 Correct 6 ms 3064 KB Output is correct
37 Correct 8 ms 3084 KB Output is correct
38 Correct 9 ms 3212 KB Output is correct
39 Correct 7 ms 3232 KB Output is correct
40 Correct 6 ms 3116 KB Output is correct
41 Correct 7 ms 3136 KB Output is correct
42 Correct 6 ms 3136 KB Output is correct
43 Correct 4 ms 2628 KB Output is correct
44 Correct 5 ms 2892 KB Output is correct
45 Correct 6 ms 3264 KB Output is correct
46 Correct 6 ms 3100 KB Output is correct
47 Correct 6 ms 3124 KB Output is correct
48 Correct 6 ms 3236 KB Output is correct
49 Correct 4 ms 2760 KB Output is correct
50 Correct 6 ms 3136 KB Output is correct
51 Correct 5 ms 3136 KB Output is correct
52 Correct 5 ms 3016 KB Output is correct
53 Correct 5 ms 3068 KB Output is correct
54 Correct 4 ms 3124 KB Output is correct
55 Correct 3 ms 3092 KB Output is correct
56 Correct 3 ms 3132 KB Output is correct