Submission #18413

#	Time	Username	Problem	Language	Result	Execution time	Memory
18413		suhgyuho_william	구간 성분 (KOI15_interval)	C++98	100 / 100	475 ms	1980 KiB

interval

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

#define Asize 7
#define MOD 4

int N,M;
int a[1510],b[1510],tmp[1510];
char s[1510];
struct data{
	long long a[Asize];

	bool operator<(const data x)const{
		int i;

		for(i=0; i<Asize; i++){
			if(x.a[i] != a[i]) return a[i] < x.a[i];
		}
		return false;
	}
};
struct data2{
	long long a[26];
}cnt1[1510],cnt2[1510];
data t;
map<data,bool> Map;
long long square[10];

void setting(){
	int i,j,k;

	square[0] = 1;
	for(i=1; i<MOD; i++) square[i] = square[i-1]*1501;
	scanf("%s",s);
	N = strlen(s);
	for(i=1; i<=N; i++) a[i] = s[i-1]-'a';
	scanf("%s",s);
	M = strlen(s);
	for(i=1; i<=M; i++) b[i] = s[i-1]-'a';
	if(N > M){
		for(i=1; i<=N; i++) tmp[i] = a[i];
		for(i=1; i<=M; i++) a[i] = b[i];
		for(i=1; i<=N; i++) b[i] = tmp[i];
		swap(N,M);
	}

	for(i=1; i<=N; i++){
		for(j=0; j<26; j++) cnt1[i].a[j] = cnt1[i-1].a[j];
		cnt1[i].a[a[i]]++;
	}
	for(i=1; i<=M; i++){
		for(j=0; j<26; j++) cnt2[i].a[j] = cnt2[i-1].a[j];
		cnt2[i].a[b[i]]++;
	}
}

int main(){
	int i,j,k;
	//freopen("input.txt","r",stdin);

	setting();

	for(i=N-1; i>=0; i--){
		Map.clear();
		for(j=1; j+i<=M; j++){
			for(k=0; k<Asize; k++) t.a[k] = 0;
			for(k=0; k<26; k++) t.a[k/MOD] += ((cnt2[j+i].a[k]-cnt2[j-1].a[k])*square[k%MOD]);
			Map[t] = true;
		}
		for(j=1; j+i<=N; j++){
			for(k=0; k<Asize; k++) t.a[k] = 0;
			for(k=0; k<26; k++) t.a[k/MOD] += ((cnt1[j+i].a[k]-cnt1[j-1].a[k])*square[k%MOD]);
			if(Map.find(t) != Map.end()){
				printf("%d",i+1);
				return 0;
			}
		}
	}

	printf("0");

	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39