Submission #20885

#	Time	Username	Problem	Language	Result	Execution time	Memory
20885		14kg	구간 성분 (KOI15_interval)	C++11	100 / 100	796 ms	1660 KiB

interval

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39