oj.uz

Submission #235020

# Submission time Handle Problem Language Result Execution time Memory
235020 2020-05-26T18:24:15 Z Nodir_Bobiev Languages (IOI10_languages) C++17
82 / 100
 334 ms 12248 KB 
#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];
map < long long, set < 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());
		if( langs[wrd].size() == 1 ){
			int res = language(*langs[wrd].begin());
			for( auto wrd: wrds ){
				langs[wrd].insert(res);
			}
			return;
		}
	}
	int mx = 0;
	for( int i = 0; i < 56; i ++ ){
		if( cnt[i] > cnt[mx] )
			mx = i;
	}
	int res = language(mx);
	for( auto wrd: wrds ){
		langs[wrd].insert(res);
	}
	//cout << "passed " << COUNTER << ' ' << wrd.size() << ' ' << probel << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 12248 KB Output is correct

Subtask #2
52.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 334 ms 12184 KB Output is partially correct - 75.87%