oj.uz

Submission #417760

# Submission time Handle Problem Language Result Execution time Memory
417760 2021-06-04T08:50:53 Z 장태환(#7548) RPS string (innopolis2021_final_C) C++17
16 / 100
 2000 ms 35544 KB 
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
int psum[500100][3];
int rpsum[500100][3];
int lac[500100][3];
int rlac[500100][3];
int lposs[500100][3];
int rlposs[500100][3];
int arr[500100];
int wi[3]={1,2,0};
int lo[3]={2,0,1};
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        memset(psum,0,sizeof(psum));
          memset(rpsum,0,sizeof(rpsum));
            memset(lac,0,sizeof(lac));  memset(rlac,0,sizeof(rlac));  memset(lposs,0,sizeof(lposs));  memset(rlposs,0,sizeof(rlposs));
        int N;
        cin >> N;
        string s;
        cin >> s;
        int i;
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='r')
                arr[i]=0;
            else if(s[i]=='p')
                arr[i]=1;
            else
                arr[i]=2;
        }
        for(i=1;i<=s.size();i++)
        {
            int j;
            for(j=0;j<3;j++)
            {
                psum[i][j]=psum[i-1][j];
                lac[i][j]=lac[i-1][j];
            }
            psum[i][arr[i-1]]++;
            lac[i][arr[i-1]]=i;
            for(j=0;j<3;j++)
            {
                lposs[i][j]=lposs[lac[i-1][lo[j]]][j];
                int psumc=psum[i-1][j]-psum[lac[i-1][lo[j]]][j];
                int psumw=psum[i-1][wi[j]]-psum[lac[i-1][lo[j]]][wi[j]];
                if(psumc&&!psumw)
                {
                    lposs[i][j]++;
                }
            }
        }
        psum[s.size()+1][0]=0;
        psum[s.size()+1][1]=0;
        psum[s.size()+1][2]=0;
        rlac[s.size()+1][0]=s.size()+1;
        rlac[s.size()+1][1]=s.size()+1;
        rlac[s.size()+1][2]=s.size()+1;
        rlposs[s.size()+1][0]=0;
        rlposs[s.size()+1][1]=0;
        rlposs[s.size()+1][2]=0;
        for(i=s.size();i>0;i--)
        {
            int j;
            for(j=0;j<3;j++)
            {
                rpsum[i][j]=rpsum[i+1][j];
                rlac[i][j]=rlac[i+1][j];
            }
            rpsum[i][arr[i-1]]++;
            rlac[i][arr[i-1]]=i;

            for(j=0;j<3;j++)
            {
                rlposs[i][j]=rlposs[rlac[i+1][lo[j]]][j];
                int psumc=rpsum[i+1][j]-rpsum[rlac[i+1][lo[j]]][j];
                int psumw=rpsum[i+1][wi[j]]-rpsum[rlac[i+1][lo[j]]][wi[j]];
                if(psumc&&!psumw)
                {
                    rlposs[i][j]++;
                }
            }

        }
        for(i=0;i<s.size();i++)
        {
            if(N==1)
            {
                int possl=!psum[i][wi[arr[i]]]||psum[i][lo[arr[i]]];
                int possr=!rpsum[i+2][wi[arr[i]]]||rpsum[i+2][lo[arr[i]]];
                cout << (possl&&possr);
            }
            else
            {
                int possl=(lposs[i+1][arr[i]]<psum[i+1][lo[arr[i]]])||i==0;
                int possr=(rlposs[i+1][arr[i]]<rpsum[i+1][lo[arr[i]]])||i==s.size()-1;
                cout << (possl&&possr);
            }
        }
        cout <<'\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
Main.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(i=1;i<=s.size();i++)
      |                 ~^~~~~~~~~~
Main.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
Main.cpp:101:74: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                 int possr=(rlposs[i+1][arr[i]]<rpsum[i+1][lo[arr[i]]])||i==s.size()-1;
      |                                                                         ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct
31 Execution timed out 2095 ms 35524 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct
31 Execution timed out 2095 ms 35524 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Incorrect 36 ms 35532 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct
31 Incorrect 36 ms 35532 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct
31 Execution timed out 2095 ms 35524 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #8
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35420 KB Output is correct
2 Correct 34 ms 35460 KB Output is correct
3 Correct 34 ms 35460 KB Output is correct
4 Correct 33 ms 35432 KB Output is correct
5 Correct 36 ms 35516 KB Output is correct
6 Correct 36 ms 35532 KB Output is correct
7 Correct 26 ms 35468 KB Output is correct
8 Correct 20 ms 35460 KB Output is correct
9 Correct 22 ms 35536 KB Output is correct
10 Correct 18 ms 35532 KB Output is correct
11 Correct 22 ms 35532 KB Output is correct
12 Correct 19 ms 35448 KB Output is correct
13 Correct 23 ms 35532 KB Output is correct
14 Correct 18 ms 35532 KB Output is correct
15 Correct 153 ms 35536 KB Output is correct
16 Correct 162 ms 35528 KB Output is correct
17 Correct 159 ms 35532 KB Output is correct
18 Correct 162 ms 35424 KB Output is correct
19 Correct 153 ms 35472 KB Output is correct
20 Correct 159 ms 35492 KB Output is correct
21 Correct 150 ms 35456 KB Output is correct
22 Correct 152 ms 35532 KB Output is correct
23 Correct 26 ms 35544 KB Output is correct
24 Correct 17 ms 35532 KB Output is correct
25 Correct 21 ms 35532 KB Output is correct
26 Correct 17 ms 35532 KB Output is correct
27 Correct 101 ms 35532 KB Output is correct
28 Correct 55 ms 35532 KB Output is correct
29 Correct 104 ms 35532 KB Output is correct
30 Correct 63 ms 35472 KB Output is correct
31 Execution timed out 2095 ms 35524 KB Time limit exceeded
32 Halted 0 ms 0 KB -