oj.uz

Submission #60869

# Submission time Handle Problem Language Result Execution time Memory
60869 2018-07-24T21:37:19 Z spencercompton Languages (IOI10_languages) C++14
94 / 100
 9653 ms 17588 KB 
#include <stdlib.h>
#include <stdio.h>
#include <bits/stdc++.h>
#include "grader.h"
#include "lang.h"
using namespace std;
#define SZ 100
typedef int ll;
int tot[56];
unordered_map<ll, int> par[56];
bool f = true;
int totp[56];
double parsq[56];
void excerpt(int *E) {
	// cout << "A " << endl;
	if(f){
			for(int j = 0; j<56; j++){
				parsq[j] = 0.0;
				totp[j] = 0;
			}
		f = false;
	}
	pair<double, int> best = make_pair(655360.0,0);
	ll li4[197];
	int point = 0;
	for(int i = 0; i<100; i++){
		int hsh1 = (655360LL * ((ll)E[i-1]+1)+ E[i]);
		if(i>0){
 
			li4[point++] = (hsh1);
		}
		if(i>1){
			hsh1 += 496726597*E[i-2];
			li4[point++] = (hsh1);
		}
	}
	int siz = point;
	sort(li4,li4+siz);
	pair<ll, int> li3[point];
	point = 0;
	for(int i = 0; i<siz; i++){
		if(i==0 || li4[i-1]!=li4[i]){
			int cnt = 0;
			for(int j = i; j<siz && li4[j]==li4[i]; j++){
				cnt++;
			}
			li3[point++] = (make_pair(li4[i],cnt));
		}
	}
	// cout << "B " << endl;
	bool fir = true;
	for(int i = 0; i<56; i++){
		if(totp[i]==0){
			continue;
		}
		double now = 0.0;
		double now2 = parsq[i];
		for(int j = 0; j<point; j++){
			ll pp = li3[j].first;
			double f1 = 0.0;
			if(par[i].find(pp)!=par[i].end()){
				f1 = par[i][pp];
			}
			f1 /= (double)totp[i];
			double f2 = (double)li3[j].second / siz;
			now2 -= f1 * f1;
			now2 += (f1-f2) * (f1-f2);
		}
		if(fir){
			best = make_pair(now2,i);
			fir = false;
		}
		best = min(best,make_pair(now2,i));
	}
	// cout << "C " << endl;
	int res = language(best.second);
	int og = totp[res];
	for(int i = 0; i<point; i++){
		if(par[res].find(li3[i].first)==par[res].end()){
			par[res][li3[i].first] = 0;
		}
		else if(og>0){
			double ff = (double)(par[res][li3[i].first]) / (double)og;
			parsq[res] -= ff*ff;
		}
		par[res][li3[i].first] += li3[i].second;
		totp[res] += li3[i].second;
	}
	// cout << "D"  << endl;
	double ff = og;
	parsq[res] *= og;
	parsq[res] *= og;
	parsq[res] /= totp[res];
	parsq[res] /= totp[res];
	for(int i = 0; i<point; i++){
		double ff = (double)(par[res][li3[i].first]) / (double)totp[res];
		parsq[res] += ff*ff;
	}
}

Compilation message

lang.cpp: In function 'void excerpt(int*)':
lang.cpp:56:10: warning: unused variable 'now' [-Wunused-variable]
   double now = 0.0;
          ^~~
lang.cpp:90:9: warning: unused variable 'ff' [-Wunused-variable]
  double ff = og;
         ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9280 ms 17588 KB Output is correct

Subtask #2
64.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 9653 ms 17420 KB Output is partially correct - 86.31%