oj.uz

Submission #245143

# Submission time Handle Problem Language Result Execution time Memory
245143 2020-07-05T15:06:42 Z urd05 구간 성분 (KOI15_interval) C++14
100 / 100
 402 ms 106232 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 false;
}

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].reserve(n+1-i);
    }
    for(int i=1;i<=m;i++) {
        bin[i].reserve(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].push_back(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].push_back(just);
        }
    }
    for(int i=n;i>0;i--) {
        sort(ain[i].begin(),ain[i].begin()+n+1-i,comp);
    }
    for(int i=m;i>0;i--) {
        sort(bin[i].begin(),bin[i].begin()+m+1-i,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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10112 KB Output is correct
2 Correct 37 ms 10112 KB Output is correct
3 Correct 36 ms 12160 KB Output is correct
4 Correct 28 ms 12160 KB Output is correct
5 Correct 45 ms 12160 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 47480 KB Output is correct
2 Correct 176 ms 47480 KB Output is correct
3 Correct 172 ms 47480 KB Output is correct
4 Correct 168 ms 47608 KB Output is correct
5 Correct 172 ms 47608 KB Output is correct
6 Correct 172 ms 47480 KB Output is correct
7 Correct 177 ms 47488 KB Output is correct
8 Correct 174 ms 47584 KB Output is correct
9 Correct 174 ms 47568 KB Output is correct
10 Correct 169 ms 47480 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 68088 KB Output is correct
2 Correct 397 ms 106228 KB Output is correct
3 Correct 390 ms 106104 KB Output is correct
4 Correct 348 ms 106156 KB Output is correct
5 Correct 402 ms 106232 KB Output is correct