oj.uz

Submission #20885

# Submission time Handle Problem Language Result Execution time Memory
20885 2017-03-04T15:48:58 Z 14kg 구간 성분 (KOI15_interval) C++11
100 / 100
 796 ms 1660 KB 
#include <stdio.h>
#include <string.h>
#include <map>

using namespace std;
struct STRING {
	int cnt[27];

	bool operator<(const STRING &t) const {
		for (int i = 1; i <= 26; i++)
			if (cnt[i] != t.cnt[i]) return cnt[i] < t.cnt[i];
		return false;
	}
	void clear() {
		for (int i = 1; i <= 26; i++) cnt[i] = 0;
	}
};
int a_len, b_len, a[1501], b[1501];
map<STRING, bool> M;

int input(int *in) {
	int len;
	char temp[1510];

	scanf("%s", temp + 1), len = strlen(temp + 1);
	for (int i = 1; i <= len; i++) in[i] = temp[i] - 'a' + 1;
	return len;
}
int main() {
	STRING temp;
	a_len = input(a), b_len = input(b);

	for (int L = (a_len < b_len ? a_len : b_len); L >= 1; L--) {
		M.clear(), temp.clear();
		for (int i = 1; i < L; i++) temp.cnt[a[i]]++;
		for (int i = 1; i <= a_len - L + 1; i++) {
			temp.cnt[a[i - 1]]--, temp.cnt[a[i + L - 1]]++;
			M[temp] = true;
		}

		temp.clear();
		for (int i = 1; i < L; i++) temp.cnt[b[i]]++;
		for (int i = 1; i <= b_len - L + 1; i++) {
			temp.cnt[b[i - 1]]--, temp.cnt[b[i + L - 1]]++;
			if (M[temp]) { printf("%d", L); return 0; }
		}
	} printf("0");
}

Compilation message

interval.cpp: In function 'int input(int*)':
interval.cpp:25:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", temp + 1), len = strlen(temp + 1);
                                               ^

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1396 KB Output is correct
2 Correct 29 ms 1320 KB Output is correct
3 Correct 0 ms 1188 KB Output is correct
4 Correct 0 ms 1188 KB Output is correct
5 Correct 66 ms 1396 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 1528 KB Output is correct
2 Correct 329 ms 1528 KB Output is correct
3 Correct 333 ms 1528 KB Output is correct
4 Correct 279 ms 1528 KB Output is correct
5 Correct 333 ms 1528 KB Output is correct
6 Correct 336 ms 1528 KB Output is correct
7 Correct 309 ms 1528 KB Output is correct
8 Correct 299 ms 1528 KB Output is correct
9 Correct 316 ms 1528 KB Output is correct
10 Correct 333 ms 1528 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1188 KB Output is correct
2 Correct 606 ms 1660 KB Output is correct
3 Correct 489 ms 1528 KB Output is correct
4 Correct 13 ms 1188 KB Output is correct
5 Correct 796 ms 1660 KB Output is correct