Submission #67939

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
67939	2018-08-15T14:55:51 Z	mhs4670	Languages (IOI10_languages)	C	65 / 100	532 ms	2116 KB

lang

#include <stdlib.h>
#include <stdio.h>
#include<string.h>

#include "grader.h"
#include "lang.h"

#define SZ 100
#define WORD 65536
#define LEARN 800
#define CLASSIFY 4
#define LANGUAGE 56

//int prev[1100000];
int cnt;
int frequency[LANGUAGE][WORD];
//int done[LANGUAGE];
int show[WORD];
int space = -1;
int word[LANGUAGE][100][CLASSIFY];
int wordFrequency[LANGUAGE][100];
int wordIndex[LANGUAGE];

struct st{
	int ori, index;
};
int comp(const void *a, const void *b){
	struct st n1 = *(struct st *)a;
	struct st n2 = *(struct st *)b;
	if (n1.ori > n2.ori)return -1;
	else if (n1.ori < n2.ori)return 1;
	return 0;
}
void findSpaceValue(int *show){
	int max = 0, val = 0;
	for (int i = 0; i < WORD; i++){
		if (show[i] > max)max = show[i], val = i;
	}
	space = val;
	//sort using show value
	/*struct st stTemp[WORD];
	for (int i = 0; i < WORD; i++){
		stTemp[i].index = i;
		stTemp[i].ori = show[i];
	}
	qsort(stTemp, WORD, sizeof(stTemp[0]), comp);*/
	//for (int i = 0; i < 100; i++){
	//	printf("index:%d, frequency:%d\n", stTemp[i].index, stTemp[i].ori);
	//}
}
void excerpt(int *E) {
	//prev[E[0]] = language(prev[E[0]]);
	//printf("cnt:%d\n", cnt);
	int ans;
	if (cnt++ < LEARN){
		ans = language(0);
		//set array of show, frequency
		int temp[WORD];
		memset(temp, 0, sizeof(temp));
		for (int i = 0; i < SZ; i++){
			temp[E[i]] = 1;
			//frequency[ans][E[i]] = 1;
		}
		for (int i = 0; i < WORD; i++){
			if (temp[i])show[i]++, frequency[ans][i] = 1;
		}
		//find integer of 'space'
		if (cnt == 50){
			findSpaceValue(show);
		}
		if (space != -1){
			for (int i = 0; i < SZ; i++){
				if (E[i] == space){
					int start = i + 1;
					int cnt = 0;
					while (start < SZ&&E[start] != 32)cnt++, start++;
					if (start == SZ || cnt > CLASSIFY || !cnt)continue;
					int len = cnt;
					int compArr[CLASSIFY];
					start = i + 1;
					for (int j = 0; j < len; j++, start++){
						compArr[j] = E[start];
					}
					int right = 1;
					for (int j = 0; j < wordIndex[ans]; j++){
						right = 1;
						for (int k = 0; k < len; k++){
							if (word[ans][j][k] != compArr[k]){
								right = 0; break;
							}
						}
						if (right){
							wordFrequency[ans][j]++; break;
						}
					}
					if (!wordIndex[ans] || !right){
						for (int k = 0; k < len; k++){
							word[ans][wordIndex[ans]][k] = compArr[k];
						}
						wordIndex[ans]++;
					}
				}
			}
		}
	}
	else{
		//int max = 0, L = 0;
		struct st temp[LANGUAGE];
		memset(temp, 0, sizeof(temp));
		for (int i = 0; i < LANGUAGE; i++){
			int cnt = 0;
			for (int j = 0; j < SZ; j++){
				if (frequency[i][E[j]])cnt++;
			}
			temp[i].index = i;
			temp[i].ori = cnt;
			//if (cnt > max)max = cnt, L = i;
		}
		qsort(temp, LANGUAGE, sizeof(temp[0]), comp);
		/*for (int i = 0; i < LANGUAGE; i++){
			printf("%d ", temp[i]);
			}
			printf("//\n");*/
		//ans = language(L);
		int sameCnt = 1;
		for (int i = 1; i < LANGUAGE; i++){
			if (temp[0].ori == temp[i].ori)sameCnt++;
			else break;
		}
		if (sameCnt == 1)language(temp[0].index);
		else{
			int howManyWord[LANGUAGE];
			memset(howManyWord, 0, sizeof(howManyWord));
			for (int z = 0; z < sameCnt; z++){
				int wordCnt = 0;
				//int max = 0, val = 0;
				/*for (int j = 0; j < SZ; j++){
					if (wordFrequency[temp[z].index][j]>max)max = wordFrequency[temp[z].index][j], val = j;
				}*/
				for (int i = 0; i < SZ; i++){
					if (E[i] == space){
						int start = i + 1;
						int cnt = 0;
						while (start < SZ&&E[start] != 32)cnt++, start++;
						if (start == SZ || cnt > CLASSIFY || !cnt)continue;
						int len = cnt;
						int compArr[CLASSIFY];
						start = i + 1;
						for (int j = 0; j < len && E[start] != 32; j++, start++){
							compArr[j] = E[start];
						}
						for (int m = 0; m < wordIndex[temp[z].index]; m++){
							int right = 1;
							for (int k = 0; k < len; k++){
								if (word[temp[z].index][m][k] != compArr[k]){
									right = 0; break;
								}
							}
							if (right){
								//language(temp[z].index); return;
								wordCnt++; continue;
							}
						}
					}
				}
				howManyWord[temp[z].index] = wordCnt;
			}
			//language(temp[0].index);
			int max = 0, val = 0;
			for (int i = 0; i < LANGUAGE; i++){
				if (howManyWord[i] > max)max = howManyWord[i], val = i;
			}
			language(val);
		}
	}


}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	532 ms	2044 KB	Output is correct

Subtask #2

35.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	423 ms	2116 KB	Output is partially correct - 60.31%