oj.uz

Submission #245136

# Submission time Handle Problem Language Result Execution time Memory
245136 2020-07-05T14:47:46 Z urd05 구간 성분 (KOI15_interval) C++14
0 / 100
 491 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

struct Save {
    long long cnt[6];
};

void add(Save* one,char x) {
    int pos=(x-'a')/5;
    long long gop=1;
    for(int i=0;i<(x-'a')%5;i++) {
        gop*=1600;
    }
    (*one).cnt[pos]+=gop;
}

bool comp(Save a,Save b) {
    for(int i=0;i<6;i++) {
        if (a.cnt[i]<b.cnt[i]) {
            return true;
        }
        if (a.cnt[i]>b.cnt[i]) {
            return false;
        }
    }
    return true;
}

char a[1501];
char b[1501];
vector<Save> ain[1501];
vector<Save> bin[1501];

int main(void) {
    int n,m;
    scanf("%s\n",a);
    scanf("%s",b);
    n=strlen(a);
    m=strlen(b);
    for(int i=1;i<=n;i++) {
        ain[i].resize(n+1-i);
    }
    for(int i=1;i<=m;i++) {
        bin[i].resize(m+1-i);
    }
    for(int i=0;i<n;i++) {
        Save just;
        memset(just.cnt,0,sizeof(just.cnt));
        for(int j=i;j<n;j++) {
            add(&just,a[j]);
            ain[j-i+1][i]=just;
        }
    }
    for(int i=0;i<m;i++) {
        Save just;
        memset(just.cnt,0,sizeof(just.cnt));
        for(int j=i;j<m;j++) {
            add(&just,b[j]);
            bin[j-i+1][i]=just;
        }
    }
    for(int i=1;i<=n;i++) {
        sort(ain[i].begin(),ain[i].end(),comp);
    }
    for(int i=1;i<=m;i++) {
        sort(bin[i].begin(),bin[i].end(),comp);
    }
    for(int i=min(n,m);i>0;i--) {
        int asz=n+1-i;
        int bsz=m+1-i;
        int aind=0;
        int bind=0;
        while (aind<asz&&bind<bsz) {
            if (comp(ain[i][aind],bin[i][bind])&&comp(bin[i][bind],ain[i][aind])) {
                printf("%d",i);
                return 0;
            }
            if (comp(ain[i][aind],bin[i][bind])) {
                aind++;
            }
            else {
                bind++;
            }
        }
    }
    printf("0");
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s\n",a);
     ~~~~~^~~~~~~~~~
interval.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",b);
     ~~~~~^~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Runtime error 8 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 20344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 487 ms 96144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 491 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -