Submission #235036

#	Time	Username	Problem	Language	Result	Execution time	Memory
235036		Nodir_Bobiev	Languages (IOI10_languages)	C++17	95 / 100	1080 ms	12188 KiB

lang

#include <stdlib.h>
#include <stdio.h>
 
#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
using namespace std;
 
const long long prime = 70207;
const long long mod = 1000000007;
 
long long probel, pows[200];
int COUNTER, symbols[100000], symbcnt[100][100000], langcnt[100];
map < long long, vector < int > > langs;

void init(){
	pows[0] = 1;
	for( int i = 1; i < 111; i ++ ){
		pows[i] = pows[i-1] * prime % mod;
	}
}
long long shifr(vector < int > vc){
	long long res = 0;
	for( size_t i = 0; i < vc.size(); i ++ ){
		res += pows[i] * vc[i];
		res %= mod;
	}
	return res;
}
void excerpt(int*E){
	COUNTER ++;
	if( COUNTER == 1 )init();
	for( int i = 0; i < 100; i ++ ){
		symbols[E[i]]++;
		if(symbols[E[i]] > symbols[probel])
			probel = E[i];
	}
	vector < long long > wrds;
	vector < int > wrd;
	for( int i = 0; i < 100; i ++ ){
		if( E[i] == probel ){
			if( wrd.empty() == false ){
				wrds.push_back(shifr(wrd));
				wrd.clear();
			}
		}
		else{
			wrd.push_back(E[i]);
		}
	}if( !wrd.empty())wrds.push_back(shifr(wrd));
	
	double cnt[100] = {};
	for( auto wrd: wrds){
		double app = 100;
		for( auto lang: langs[wrd] )
			cnt[lang] += (app/langs[wrd].size());
	}
	for(int i = 0; i < 100; i ++ ){
		if( E[i] == probel ) continue;
		for( int j = 0; j < 56; j ++ ){
			cnt[j] += .1*symbcnt[j][i]/langcnt[j];
		}
	}
	int mx = 0;
	for( int i = 0; i < 56; i ++ ){
		if( cnt[i] > cnt[mx] )
			mx = i;
	}
	int res = language(mx);
	langcnt[res]++;
	for( auto wrd: wrds ){
		langs[wrd].push_back(res);
	}
	for( int i = 0; i < 100; i++){
		symbcnt[res][E[i]]++;
	}
	//cout << "passed " << COUNTER << ' ' << wrd.size() << ' ' << probel << endl;
}	

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