oj.uz

답안 #18040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18040 2016-01-18T15:28:42 Z tncks0121 구간 성분 (KOI15_interval) C++14
100 / 100
 518 ms 1716 KB 
#define _CRT_SECURE_NO_WARNINGS
      
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
      
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

char S[1505], T[1505];
int N, M;

int main() {
	scanf("%s%s", S, T);
	N = strlen(S);
	M = strlen(T);

	if(N > M) {
		swap(S, T);
		swap(N, M);
	}

	for(int i = 0; i < N; i++) S[i] -= 'a';
	for(int i = 0; i < M; i++) T[i] -= 'a';

	for(int len = N; len >= 1; len--) {
		set< vector<int> > Q;
		{
			vector<int> c(26);
			for(int j = 0; j < len-1; j++) c[S[j]]++;
			for(int i = 0, j = len-1; j < N; i++, j++) {
				c[S[j]]++;
				Q.insert(c);
				c[S[i]]--;
			}
		}
		{
			vector<int> c(26);
			for(int j = 0; j < len-1; j++) c[T[j]]++;
			for(int i = 0, j = len-1; j < M; i++, j++) {
				c[T[j]]++;
				if(Q.find(c) != Q.end()) {
					printf("%d\n", len);
					return 0;
				} 
				c[T[i]]--;
			}
		}
	}

	puts("0");
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Correct 0 ms 1584 KB Output is correct
3 Correct 0 ms 1584 KB Output is correct
4 Correct 2 ms 1584 KB Output is correct
5 Correct 0 ms 1584 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1584 KB Output is correct
2 Correct 21 ms 1584 KB Output is correct
3 Correct 0 ms 1584 KB Output is correct
4 Correct 0 ms 1584 KB Output is correct
5 Correct 51 ms 1584 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 1716 KB Output is correct
2 Correct 230 ms 1716 KB Output is correct
3 Correct 220 ms 1716 KB Output is correct
4 Correct 216 ms 1716 KB Output is correct
5 Correct 223 ms 1716 KB Output is correct
6 Correct 219 ms 1716 KB Output is correct
7 Correct 220 ms 1716 KB Output is correct
8 Correct 217 ms 1716 KB Output is correct
9 Correct 225 ms 1716 KB Output is correct
10 Correct 223 ms 1716 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1584 KB Output is correct
2 Correct 427 ms 1716 KB Output is correct
3 Correct 368 ms 1716 KB Output is correct
4 Correct 13 ms 1584 KB Output is correct
5 Correct 518 ms 1716 KB Output is correct