답안 #69053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69053	2018-08-19T15:33:05 Z	mhs4670	Languages (IOI10_languages)	C	92 / 100	948 ms	22268 KB

lang

#if 01
 
#include <stdlib.h>
#include <stdio.h>
 
#include "grader.h"
#include "lang.h"
 
#define SZ 100
#define M (100003)
#define LANG (56)
#define P (65537)
 
typedef long long ll;
const int roll = 3;
 
ll save[SZ + 1];
//int cnt[LANG][P];
int hcnt[LANG][M];
int vote[LANG];
ll pre_pow[3];
int init;
 
ll hash(int *E){
	ll hash_value = 0;
	//ll p_pow = 1;
	for (int i = 0; i < roll; i++){
		hash_value = (hash_value + E[i] * pre_pow[i]) % M;
		//p_pow = (p_pow*P) % M;
	}
	return hash_value;
}
void excerpt(int *E) {
  if(!init){
    init=1;
    pre_pow[0]=1;
    pre_pow[1]=P;
    pre_pow[2]=(P*P)%M;
  }
	for (int i = 0; i < SZ - roll + 1; i++){
		save[i] = hash(E + i);
	}
	for (int i = 0; i < LANG; i++){
		vote[i] = 0;
		for (int j = 0; j < SZ; j++){
			//if (cnt[i][E[j]])vote[i]++;
			if (i < SZ - roll + 1)
				if (hcnt[i][save[j]])vote[i]++;
		}
	}
	int guess = 0, max = 0;
	for (int i = 0; i < LANG; i++){
		if (max < vote[i])guess = i, max = vote[i];
	}
	int ans = language(guess);
	for (int i = 0; i < SZ; i++){
		//cnt[ans][i]++;
		if (i<SZ - roll + 1) hcnt[ans][save[i]]++;
	}
}
 
#endif

Compilation message

lang.c: In function 'excerpt':
lang.c:38:18: warning: integer overflow in expression [-Woverflow]
     pre_pow[2]=(P*P)%M;
                  ^

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	948 ms	22268 KB	Output is correct

Subtask #2

62.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	866 ms	22264 KB	Output is partially correct - 84.72%