oj.uz

답안 #937999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937999 2024-03-04T17:30:52 Z kim Linear Garden (IOI08_linear_garden) C++17
100 / 100
 16 ms 10508 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int n,m,qs[1000005],cnt[5],pw[1000005]={1};
string s;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>s;
    set<int> Set;
    Set.insert(0);
    cnt[2]=1;
    for(int i=1;i<=n;++i){
        pw[i]=(pw[i-1]<<1)%m;
        qs[i]=qs[i-1]+(s[i-1]=='L'?-1:1);
        if(!cnt[qs[i]+2]++) Set.insert(qs[i]);
    }

    ll ans=1;
    for(int i=n;i>0;--i){
        if(--cnt[qs[i]+2]==0) Set.erase(qs[i]);
        int mn=*Set.rbegin()-2;
        int mx=*Set.begin()+2;
        if(s[i-1]=='L') continue;
        bool a=qs[i]-4>=mn&&qs[i]-2<=mx;
        bool b=qs[i]-3>=mn&&qs[i]-1<=mx;
        bool c=qs[i]-2>=mn&&qs[i]<=mx;
        ans=(ans+(a+c)*pw[n-i>>1])%m;
        if(b){
            ans=(ans+(a+c)*(m-1))%m;
            ans=(ans+pw[n-i+1>>1])%m;
        }
    }
    cout<<ans;

    return 0;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:30:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   30 |         ans=(ans+(a+c)*pw[n-i>>1])%m;
      |                           ~^~
linear_garden.cpp:33:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             ans=(ans+pw[n-i+1>>1])%m;
      |                         ~~~^~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 472 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 500 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1112 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4728 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5360 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5792 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6648 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 10228 KB Output is correct
2 Correct 16 ms 10232 KB Output is correct
3 Correct 15 ms 10508 KB Output is correct