oj.uz

Submission #23148

# Submission time Handle Problem Language Result Execution time Memory
23148 2017-05-03T15:50:23 Z ruhanhabib39 Languages (IOI10_languages) C++14
99 / 100
 2210 ms 6460 KB 
#include <bits/stdc++.h>
#include "grader.h"

typedef unsigned long long Long;

#define SZ 100

int has[56][(1 << 16) + 10];
std::unordered_map<Long,int> words[56];
int CC[56];
int rr[56];

struct dat {
   int c; int cc;
   dat() {
      c = cc = 0;
   }
};

dat sp;

int lf(int* E) {
   int mi = 0;
   for(int l = 0; l < 56; l++) {
      if(!CC[l]) continue;
      for(int i = 0; i < 100;) {
         int j = i;
         while(j < 100 && E[j] == E[i]) {
            j++;
         }
         int c0 = j - i;
         double freq0 = double(has[l][E[i]]) / double(CC[l]);
         double freqq = double(c0) / 100.0;
         if(has[l][E[i]] && fabs(freq0 - freqq) < 0.0322201) {
            rr[l]++;
         }
         i = j;
      }
      if(rr[l] >= rr[mi]) {
         mi = l;
      }
   }
   return mi;
}

void ff(int* E) { 
   for(int l = 0; l < 56; l++) {
      std::unordered_map<Long,int> cc;
      for(int i = 0; i < 100; ) {
         while(i < 100 && E[i] == sp.c) i++;
         Long w = 0;
         while(i < 100 && E[i] != sp.c) {
            w = (1 << 16) * w + E[i];
            i++;
         }
         cc[w]++;
         // if(words[l].find(w) != words[l].end()) {
         //    rr[l] += 3;
         // }
      }
      for(auto it : cc) {
         auto jt = words[l].find(it.first);
         if(jt == words[l].end()) continue;
         double f0 = double(jt->second)/double(CC[l]);
         double f1 = double(it.second)/100.0;
         if(fabs(f0 - f1) < 0.1) {
            rr[l]++;
         }
         if(fabs(f0 - f1) < 0.06) {
            rr[l]++;
         }
         if(fabs(f0 - f1) < 0.03) {
            rr[l]++;
         }
         if(fabs(f0 - f1) < 0.01) {
            rr[l]++;
         }
      }
   }
}

int O[100 + 10];
int LC[(1 << 16) + 10];

void excerpt(int *E) {
   memset(rr, 0, sizeof(rr));
   ff(E);
   for(int i = 0; i < 100; i++) {
      O[i] = E[i];
   }
   std::sort(E, E + 100);
   int l = language(lf(E));
   for(int i = 0; i < 100; i++) {
      has[l][E[i]]++; LC[E[i]]++;
      if(LC[E[i]] > sp.cc) {
         sp.c = E[i];
         sp.cc = LC[E[i]];
      }
   }
   for(int i = 0; i < 100; ) {
      while(i < 100 && O[i] == sp.c) i++;
      Long w = 0;
      while(i < 100 && O[i] != sp.c) {
         w = (1 << 16) * w + O[i];
         i++;
      }
      words[l][w]++;
   }
   CC[l] += 100;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2079 ms 6356 KB Output is correct

Subtask #2
69.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 2210 ms 6460 KB Output is partially correct - 90.49%