oj.uz

Submission #18096

# Submission time Handle Problem Language Result Execution time Memory
18096 2016-01-20T06:24:50 Z comet 구간 성분 (KOI15_interval) C++14
100 / 100
 525 ms 1348 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

char t[2][1510];

int main(){

	int sz[2];
	for(int i=0;i<2;i++){
		scanf("%s",t[i]);
		sz[i]=strlen(t[i]);
	}

	int n=min(sz[0],sz[1]);

	for(int i=n;i>0;i--){
		vector<char> s(30);
		set<vector<char>> S;
		for(int j=0;j<i;j++){
			s[t[0][j]-'a']++;
		}
		S.insert(s);
		for(int j=0;j<sz[0]-i;j++){
			s[t[0][j]-'a']--;
			s[t[0][j+i]-'a']++;
			S.insert(s);
		}

		s=vector<char>(30);
		for(int j=0;j<i;j++){
			s[t[1][j]-'a']++;
		}
		if(S.find(s)!=S.end()){
				printf("%d\n",i);
				return 0;
		}
		for(int j=0;j<sz[1]-i;j++){
			s[t[1][j]-'a']--;
			s[t[1][j+i]-'a']++;
			if(S.find(s)!=S.end()){
				printf("%d\n",i);
				return 0;
			}
		}
	}
	puts("0");
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1216 KB Output is correct
2 Correct 30 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 51 ms 1216 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 1216 KB Output is correct
2 Correct 233 ms 1216 KB Output is correct
3 Correct 219 ms 1216 KB Output is correct
4 Correct 219 ms 1216 KB Output is correct
5 Correct 225 ms 1216 KB Output is correct
6 Correct 221 ms 1216 KB Output is correct
7 Correct 220 ms 1216 KB Output is correct
8 Correct 220 ms 1216 KB Output is correct
9 Correct 230 ms 1216 KB Output is correct
10 Correct 227 ms 1216 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1216 KB Output is correct
2 Correct 436 ms 1348 KB Output is correct
3 Correct 377 ms 1216 KB Output is correct
4 Correct 14 ms 1216 KB Output is correct
5 Correct 525 ms 1348 KB Output is correct