oj.uz

Submission #18417

# Submission time Handle Problem Language Result Execution time Memory
18417 2016-02-01T05:08:46 Z suhgyuho_william 구간 성분 (KOI15_interval) C++
61 / 100
 789 ms 131072 KB 
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

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

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

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

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

	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]]++;
	}
	for(i=1; i<=M; i++){
		for(j=i; j<=M; j++){
			for(k=0; k<26; k++) t.a[k] = (cnt2[j].a[k]-cnt2[i-1].a[k]);
			t.cnt = j-i+1;
			Map[t] = true;
		}
	}

	for(i=N-1; i>=0; i--){
		for(j=1; j+i<=N; j++){
			for(k=0; k<26; k++) t.a[k] = (cnt1[j+i].a[k]-cnt1[j-1].a[k]);
			t.cnt = i+1;
			if(Map.find(t) != Map.end()){
				printf("%d",i+1);
				return 0;
			}
		}
	}

	printf("0");

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1556 KB Output is correct
2 Correct 0 ms 1688 KB Output is correct
3 Correct 0 ms 1688 KB Output is correct
4 Correct 2 ms 2216 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 13436 KB Output is correct
2 Correct 69 ms 11060 KB Output is correct
3 Correct 37 ms 2744 KB Output is correct
4 Correct 24 ms 1556 KB Output is correct
5 Correct 134 ms 19112 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 73232 KB Output is correct
2 Correct 578 ms 75872 KB Output is correct
3 Correct 595 ms 75080 KB Output is correct
4 Correct 600 ms 73232 KB Output is correct
5 Correct 584 ms 75740 KB Output is correct
6 Correct 576 ms 73760 KB Output is correct
7 Correct 592 ms 75740 KB Output is correct
8 Correct 597 ms 75872 KB Output is correct
9 Correct 572 ms 75872 KB Output is correct
10 Correct 570 ms 75476 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 27956 KB Output is correct
2 Memory limit exceeded 789 ms 131072 KB Memory limit exceeded
3 Halted 0 ms 0 KB -