Submission #245143

#	Time	Username	Problem	Language	Result	Execution time	Memory
245143		urd05	구간 성분 (KOI15_interval)	C++14	100 / 100	402 ms	106232 KiB

interval

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39