Submission #567224

#	Time	Username	Problem	Language	Result	Execution time	Memory
567224		tqbfjotld	Misspelling (JOI22_misspelling)	C++14	8 / 100	157 ms	8852 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define int long long

int rel[20];
int A[500005];
int B[500005];

int mem[20][26];

int func(int n, int last){
    if (mem[n][last]!=-1) return mem[n][last];
    if (n==1) return 1;
    if (rel[n-2]==1){
        return mem[n][last] = func(n-1,last);
    }
    int ans = 0;
    for (int x = 0; x<26; x++){
        if (rel[n-2]==0 && last>x){
            ans += func(n-1,x);
        }
        if (rel[n-2]==2 && last<x){
            ans += func(n-1,x);
        }
        ans %= 1000000007;
    }
    return mem[n][last] = ans;
}

 main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<m; x++){
        scanf("%lld%lld",&A[x],&B[x]);
        A[x]--; B[x]--;
    }
    int ans = 0;
    for (int x = 0; x<(int)pow(3,n-1); x++){
        int t = x;
        for (int y = 0; y<n-1; y++){
            rel[y] = t%3;
            //printf("%lld ",rel[y]);
            t/=3;
        }
        //printf("\n");
        bool can = true;
        for (int y = 0; y<m; y++){
            if (A[y]<B[y]){
                for (int z = 0; z<B[y]-A[y]; z++){
                    if (rel[A[y]+z]==0){
                        can = false;
                        break;
                    }
                    if (rel[A[y]+z]==2){
                        break;
                    }
                }
            }
            else{
                for (int z = 0; z<A[y]-B[y]; z++){
                    if (rel[B[y]+z]==2){
                        can = false;
                        break;
                    }
                    if (rel[B[y]+z]==0){
                        break;
                    }
                }
            }
        }
        if (can){
            //printf("hi\n");
            memset(mem,-1,sizeof(mem));
            for (int x = 0; x<26; x++){
                ans += func(n,x);
                ans %= 1000000007;
            }
        }
    }
    printf("%lld",ans);
}

Compilation message (stderr)

misspelling.cpp:30:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 |  main(){
      |  ^~~~
misspelling.cpp: In function 'int main()':
misspelling.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
misspelling.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%lld%lld",&A[x],&B[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11