Submission #170185

#	Time	Username	Problem	Language	Result	Execution time	Memory
170185		ics0503	Languages (IOI10_languages)	C++17	96 / 100	2193 ms	157404 KiB

lang

#include <stdlib.h>
#include <stdio.h>
#include <set>
using namespace std;

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

#define SZ 100
int num[56][65536], ccnt = 0, commonChar[65536], uniqueChar[65536];
int mod = 499973;
int num2[56][499973];
int num3[56][499973];
int dan[56][499973];
long long hash2(long long x, long long y) {
	return (x * 65536 + y) % mod;
}
long long hash3(long long x, long long y, long long z) {
	return (((x * 65536 + y) % mod)*65536 + z)%mod;
}
long long hashX(int *E, int s, int e) {
	if (s > e)return 0;
	long long res = 0, i;
	for (i = s; i <= e; i++) {
		res = (res * 65536 + E[i]) % mod;
	}
	return res;
}
int pandan(int *E) {
	int nE[222] = { 0, }, n=0, i, j;
	int js[56] = { 0, };
	for (i = 0; i < 100; i++) {
		for (j = 0; j < 56; j++) {
			js[j] += !!num[j][E[i]];
		}
	}
	for (i = 1; i < 100; i++) {
		int g = hash2(E[i - 1], E[i]);
		for (j = 0; j < 56; j++) {
			js[j] += num2[j][g];
		}
	}
	for (i = 2; i < 100; i++) {
		int g = hash3(E[i-2], E[i - 1], E[i]);
		for (j = 0; j < 56; j++) {
			js[j] += num3[j][g]*2;
		}
	}
	if (ccnt > 500) {
		int befw = 0;
		for (i = 0; i < 100; i++) {
			if (commonChar[E[i]]) {
				befw = i;
				int k = hashX(E, befw + 1, i - 1), cnt=0, cntw;
				for (j = 0; j < 56; j++) {
					js[j] += dan[j][k]*2;
					cnt += dan[j][k];
					if (dan[j][k])cntw=j;
				}
				if (cnt == 1)
					return cntw;
			}
		}
	}
	int mx = -1, mxw = 0;
	for (i = 0; i < 56; i++) if (mx < js[i])mx = js[i], mxw = i;
	return mxw;
}
int num2x[65536] = { 0, };
int max(int a, int b) {
	if (a < b)return b; return a;
}
void learn(int *E, int ans) {
	int i, j, k;
	for (i = 0; i < 100; i++) num2x[E[i]] = 0;
	for (i = 0; i < 100; i++) num2x[E[i]]++;
	for (i = 0; i < 100; i++) num[ans][E[i]] = max(num[ans][E[i]], num2x[E[i]]);
	for (i = 1; i < 100; i++) num2[ans][hash2(E[i - 1], E[i])] = 1;
	for (i = 2; i < 100; i++) num3[ans][hash3(E[i - 2], E[i - 1], E[i])] = 1;
	for (i = 0; i < 100; i++) {
		int cr = E[i];
		int cnt = 0, w = -1,CRT=0;
		for (j = 0; j < 56; j++) {
			if (num[j][cr]) {
				cnt++;
				w = j;
			}
			if (num[j][cr]>15) {
				CRT++;
			}
		}
		if(CRT>45){
			if(!commonChar[cr])
				commonChar[cr] = 1;
		}
		else {
			commonChar[cr] = 0;
		}
		uniqueChar[cr] = cnt==1?w:-1;
	}
	if (ccnt > 500) {
		int befw = 0;
		for (i = 0; i < 100; i++) {
			if (commonChar[E[i]]) {
				befw = i;
				int k = hashX(E, befw + 1, i - 1);
				if (k != 0) dan[ans][k] = 1;
			}
		}
	}
}
void excerpt(int *E) {
	int i, j;
	ccnt++;
	int ans = language(pandan(E));
	learn(E, ans);
}

Compilation message (stderr)

lang.cpp: In function 'int pandan(int*)':
lang.cpp:30:6: warning: unused variable 'nE' [-Wunused-variable]
  int nE[222] = { 0, }, n=0, i, j;
      ^~
lang.cpp:30:24: warning: unused variable 'n' [-Wunused-variable]
  int nE[222] = { 0, }, n=0, i, j;
                        ^
lang.cpp: In function 'int max(int, int)':
lang.cpp:71:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (a < b)return b; return a;
  ^~
lang.cpp:71:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (a < b)return b; return a;
                      ^~~~~~
lang.cpp: In function 'void learn(int*, int)':
lang.cpp:74:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
lang.cpp: In function 'void excerpt(int*)':
lang.cpp:113:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
lang.cpp:113:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
lang.cpp: In function 'int pandan(int*)':
lang.cpp:22:2: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
  if (s > e)return 0;
  ^~
lang.cpp: In function 'void learn(int*, int)':
lang.cpp:22:2: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
  if (s > e)return 0;
  ^~
lang.cpp: In function 'int pandan(int*)':
lang.cpp:54:47: warning: 'cntw' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int k = hashX(E, befw + 1, i - 1), cnt=0, cntw;
                                               ^~~~

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