Submission #67929

#	Time	Username	Problem	Language	Result	Execution time	Memory
67929		mhs4670	Languages (IOI10_languages)	C11	55 / 100	524 ms	2056 KiB

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

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

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;
	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 > 4 || !cnt)continue;
					int len = cnt;
					int compArr[4];
					start = i + 1;
					for (int j = 0; j < len; j++, start++){
						compArr[j] = E[start];
					}
					int right;
					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[56];
		memset(temp, 0, sizeof(temp));
		for (int i = 0; i < 56; 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, 56, sizeof(temp[0]), comp);
		/*for (int i = 0; i < 56; i++){
			printf("%d ", temp[i]);
			}
			printf("//\n");*/
		//ans = language(L);
		int sameCnt = 1;
		for (int i = 1; i < 56; i++){
			if (temp[i].ori == temp[0].ori)sameCnt++;
			else break;
		}
		if (sameCnt == 1)language(temp[0].index);
		else{
			for (int z = 0; z < sameCnt; z++){
				int max = 0, val;
				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 > 4 || !cnt)continue;
						int len = cnt;
						int compArr[4];
						start = i + 1;
						for (int j = 0; j < len && E[start] != 32; j++, start++){
							compArr[j] = E[start];
						}
						int right = 1;
						for (int k = 0; k < len; k++){
							if (word[z][val][k] != compArr[k]){
								right = 0; break;
							}
						}
						if (right){
							language(temp[z].index); return;
						}
					}
				}
			}
			language(temp[0].index);
		}
	}


}

Compilation message (stderr)

lang.c: In function 'findSpaceValue':
lang.c:37:8: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  space = val;
  ~~~~~~^~~~~
lang.c: In function 'excerpt':
lang.c:131:18: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int max = 0, val;
                  ^~~
lang.c:94:26: warning: 'right' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (!wordIndex[ans] || !right){
          ~~~~~~~~~~~~~~~~^~~~~~~~~
lang.c:37:8: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  space = val;
  ~~~~~~^~~~~
lang.c:33:15: note: 'val' was declared here
  int max = 0, val;
               ^~~

• Subtask 1: 30 / 30
• Subtask 2: 25 / 80