제출 #1330764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330764		TheMiraiTraveller0711	Languages (IOI10_languages)	C++20	컴파일 에러	0 ms	0 KiB

lang

/*
 * IOI 2010 - Language
 * N-gram approach (unigrams + bigrams + trigrams + 4-grams) with log-frequency scoring.
 *
 * Strategy:
 * - For each language L, maintain frequency hash maps for n-grams (n=1..4).
 * - For a new excerpt E, score each language as:
 *     sum over all distinct n-grams g in E of weight(n) * log(1 + freq[L][g])
 * - Choose the language with highest score.
 * - After getting correct label, update all n-gram counts.
 *
 * Memory:
 * - Unigrams: freq[56][65536] int array (~14MB)
 * - 2/3/4-grams: per-language unordered_maps (grow with data, bounded)
 *
 * Weights: higher-order grams are more discriminative.
 * W1=1, W2=3, W3=6, W4=10
 */

#include "grader.h"
#include <cstring>
#include <cmath>
#include <unordered_map>

static const int NLANGS   = 56;
static const int NSYMBOLS = 65536;

// Unigram table (fast array)
static int freq1[NLANGS][NSYMBOLS];

// Higher-order n-gram tables (hash maps per language)
static std::unordered_map<uint64_t, int> freq2[NLANGS];
static std::unordered_map<uint64_t, int> freq3[NLANGS];
static std::unordered_map<uint64_t, int> freq4[NLANGS];

static int lang_count[NLANGS];

// N-gram score weights
static const double W1 = 1.0;
static const double W2 = 3.0;
static const double W3 = 6.0;
static const double W4 = 10.0;

// Scratch buffers (static to avoid stack allocation per call)
static bool seen1[NSYMBOLS];          // for deduplicating unigrams
static int  distinct1[100];           // distinct unigrams in current excerpt
static std::unordered_map<uint64_t,int> bg_count;   // bigrams in excerpt
static std::unordered_map<uint64_t,int> tg_count;   // trigrams in excerpt
static std::unordered_map<uint64_t,int> fg_count;   // 4-grams in excerpt

void excerpt(int *E) {

    // ── Collect n-grams from E ──────────────────────────────────────────────

    int nd1 = 0;
    for (int i = 0; i < 100; i++) {
        if (!seen1[E[i]]) { seen1[E[i]] = true; distinct1[nd1++] = E[i]; }
    }

    bg_count.clear();
    for (int i = 0; i < 99; i++) {
        uint64_t k = (uint64_t)E[i] * 65536ULL + E[i+1];
        bg_count[k]++;
    }

    tg_count.clear();
    for (int i = 0; i < 98; i++) {
        uint64_t k = (uint64_t)E[i] * (65536ULL*65536ULL)
                   + (uint64_t)E[i+1] * 65536ULL
                   + E[i+2];
        tg_count[k]++;
    }

    fg_count.clear();
    for (int i = 0; i < 97; i++) {
        uint64_t k = (uint64_t)E[i]   * (65536ULL*65536ULL*65536ULL)
                   + (uint64_t)E[i+1] * (65536ULL*65536ULL)
                   + (uint64_t)E[i+2] * 65536ULL
                   + E[i+3];
        fg_count[k]++;
    }

    // ── Score each language ─────────────────────────────────────────────────

    double best_score = -1e30;
    int    best_lang  = 0;

    for (int l = 0; l < NLANGS; l++) {

        if (lang_count[l] == 0) {
            // Unseen: rank below all seen languages, use index as tie-break
            double s = -1e10 + l * 1e-6;
            if (s > best_score) { best_score = s; best_lang = l; }
            continue;
        }

        double score = 0.0;

        // Unigrams
        for (int i = 0; i < nd1; i++) {
            int f = freq1[l][distinct1[i]];
            if (f) score += W1 * log(1.0 + f);
        }

        // Bigrams
        for (auto& [k, _] : bg_count) {
            auto it = freq2[l].find(k);
            if (it != freq2[l].end()) score += W2 * log(1.0 + it->second);
        }

        // Trigrams
        for (auto& [k, _] : tg_count) {
            auto it = freq3[l].find(k);
            if (it != freq3[l].end()) score += W3 * log(1.0 + it->second);
        }

        // 4-grams
        for (auto& [k, _] : fg_count) {
            auto it = freq4[l].find(k);
            if (it != freq4[l].end()) score += W4 * log(1.0 + it->second);
        }

        if (score > best_score) { best_score = score; best_lang = l; }
    }

    // Reset seen1 scratch buffer
    for (int i = 0; i < nd1; i++) seen1[distinct1[i]] = false;

    // ── Guess and receive correct label ────────────────────────────────────

    int correct = language(best_lang);

    // ── Update model ────────────────────────────────────────────────────────

    for (int i = 0; i < 100; i++)
        freq1[correct][E[i]]++;

    for (int i = 0; i < 99; i++) {
        uint64_t k = (uint64_t)E[i] * 65536ULL + E[i+1];
        freq2[correct][k]++;
    }

    for (int i = 0; i < 98; i++) {
        uint64_t k = (uint64_t)E[i] * (65536ULL*65536ULL)
                   + (uint64_t)E[i+1] * 65536ULL
                   + E[i+2];
        freq3[correct][k]++;
    }

    for (int i = 0; i < 97; i++) {
        uint64_t k = (uint64_t)E[i]   * (65536ULL*65536ULL*65536ULL)
                   + (uint64_t)E[i+1] * (65536ULL*65536ULL)
                   + (uint64_t)E[i+2] * 65536ULL
                   + E[i+3];
        freq4[correct][k]++;
    }

    lang_count[correct]++;
}

컴파일 시 표준 에러 (stderr) 메시지

lang.cpp:32:27: error: 'uint64_t' was not declared in this scope
   32 | static std::unordered_map<uint64_t, int> freq2[NLANGS];
      |                           ^~~~~~~~
lang.cpp:24:1: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
   23 | #include <unordered_map>
  +++ |+#include <cstdint>
   24 | 
lang.cpp:32:40: error: template argument 1 is invalid
   32 | static std::unordered_map<uint64_t, int> freq2[NLANGS];
      |                                        ^
lang.cpp:32:40: error: template argument 3 is invalid
lang.cpp:32:40: error: template argument 4 is invalid
lang.cpp:32:40: error: template argument 5 is invalid
lang.cpp:33:27: error: 'uint64_t' was not declared in this scope
   33 | static std::unordered_map<uint64_t, int> freq3[NLANGS];
      |                           ^~~~~~~~
lang.cpp:33:27: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:33:40: error: template argument 1 is invalid
   33 | static std::unordered_map<uint64_t, int> freq3[NLANGS];
      |                                        ^
lang.cpp:33:40: error: template argument 3 is invalid
lang.cpp:33:40: error: template argument 4 is invalid
lang.cpp:33:40: error: template argument 5 is invalid
lang.cpp:34:27: error: 'uint64_t' was not declared in this scope
   34 | static std::unordered_map<uint64_t, int> freq4[NLANGS];
      |                           ^~~~~~~~
lang.cpp:34:27: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:34:40: error: template argument 1 is invalid
   34 | static std::unordered_map<uint64_t, int> freq4[NLANGS];
      |                                        ^
lang.cpp:34:40: error: template argument 3 is invalid
lang.cpp:34:40: error: template argument 4 is invalid
lang.cpp:34:40: error: template argument 5 is invalid
lang.cpp:47:27: error: 'uint64_t' was not declared in this scope
   47 | static std::unordered_map<uint64_t,int> bg_count;   // bigrams in excerpt
      |                           ^~~~~~~~
lang.cpp:47:27: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:47:39: error: template argument 1 is invalid
   47 | static std::unordered_map<uint64_t,int> bg_count;   // bigrams in excerpt
      |                                       ^
lang.cpp:47:39: error: template argument 3 is invalid
lang.cpp:47:39: error: template argument 4 is invalid
lang.cpp:47:39: error: template argument 5 is invalid
lang.cpp:48:27: error: 'uint64_t' was not declared in this scope
   48 | static std::unordered_map<uint64_t,int> tg_count;   // trigrams in excerpt
      |                           ^~~~~~~~
lang.cpp:48:27: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:48:39: error: template argument 1 is invalid
   48 | static std::unordered_map<uint64_t,int> tg_count;   // trigrams in excerpt
      |                                       ^
lang.cpp:48:39: error: template argument 3 is invalid
lang.cpp:48:39: error: template argument 4 is invalid
lang.cpp:48:39: error: template argument 5 is invalid
lang.cpp:49:27: error: 'uint64_t' was not declared in this scope
   49 | static std::unordered_map<uint64_t,int> fg_count;   // 4-grams in excerpt
      |                           ^~~~~~~~
lang.cpp:49:27: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:49:39: error: template argument 1 is invalid
   49 | static std::unordered_map<uint64_t,int> fg_count;   // 4-grams in excerpt
      |                                       ^
lang.cpp:49:39: error: template argument 3 is invalid
lang.cpp:49:39: error: template argument 4 is invalid
lang.cpp:49:39: error: template argument 5 is invalid
lang.cpp: In function 'void excerpt(int*)':
lang.cpp:60:14: error: request for member 'clear' in 'bg_count', which is of non-class type 'int'
   60 |     bg_count.clear();
      |              ^~~~~
lang.cpp:62:9: error: 'uint64_t' was not declared in this scope
   62 |         uint64_t k = (uint64_t)E[i] * 65536ULL + E[i+1];
      |         ^~~~~~~~
lang.cpp:62:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:63:18: error: 'k' was not declared in this scope
   63 |         bg_count[k]++;
      |                  ^
lang.cpp:66:14: error: request for member 'clear' in 'tg_count', which is of non-class type 'int'
   66 |     tg_count.clear();
      |              ^~~~~
lang.cpp:68:9: error: 'uint64_t' was not declared in this scope
   68 |         uint64_t k = (uint64_t)E[i] * (65536ULL*65536ULL)
      |         ^~~~~~~~
lang.cpp:68:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:71:18: error: 'k' was not declared in this scope
   71 |         tg_count[k]++;
      |                  ^
lang.cpp:74:14: error: request for member 'clear' in 'fg_count', which is of non-class type 'int'
   74 |     fg_count.clear();
      |              ^~~~~
lang.cpp:76:9: error: 'uint64_t' was not declared in this scope
   76 |         uint64_t k = (uint64_t)E[i]   * (65536ULL*65536ULL*65536ULL)
      |         ^~~~~~~~
lang.cpp:76:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:80:18: error: 'k' was not declared in this scope
   80 |         fg_count[k]++;
      |                  ^
lang.cpp:106:29: error: 'begin' was not declared in this scope
  106 |         for (auto& [k, _] : bg_count) {
      |                             ^~~~~~~~
lang.cpp:106:29: note: suggested alternatives:
In file included from /usr/include/c++/13/unordered_map:42,
                 from lang.cpp:23:
/usr/include/c++/13/bits/range_access.h:114:37: note:   'std::begin'
  114 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
      |                                     ^~~~~
In file included from /usr/include/c++/13/bits/ranges_util.h:34,
                 from /usr/include/c++/13/tuple:44,
                 from /usr/include/c++/13/bits/hashtable_policy.h:34,
                 from /usr/include/c++/13/bits/hashtable.h:35,
                 from /usr/include/c++/13/bits/unordered_map.h:33,
                 from /usr/include/c++/13/unordered_map:41:
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   'std::ranges::__cust::begin'
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
In file included from /usr/include/c++/13/bits/stl_iterator_base_types.h:71,
                 from /usr/include/c++/13/bits/stl_algobase.h:65,
                 from /usr/include/c++/13/bits/specfun.h:43,
                 from /usr/include/c++/13/cmath:3699,
                 from lang.cpp:22:
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note:   'std::ranges::__cust_access::begin'
  984 |     void begin(const auto&) = delete;
      |          ^~~~~
lang.cpp:106:29: error: 'end' was not declared in this scope
  106 |         for (auto& [k, _] : bg_count) {
      |                             ^~~~~~~~
lang.cpp:106:29: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:116:37: note:   'std::end'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   'std::ranges::__cust::end'
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   'std::ranges::__cust_access::end'
  137 |     void end(const auto&) = delete;
      |          ^~~
lang.cpp:107:32: error: request for member 'find' in 'freq2[l]', which is of non-class type 'int'
  107 |             auto it = freq2[l].find(k);
      |                                ^~~~
lang.cpp:108:32: error: request for member 'end' in 'freq2[l]', which is of non-class type 'int'
  108 |             if (it != freq2[l].end()) score += W2 * log(1.0 + it->second);
      |                                ^~~
lang.cpp:112:29: error: 'begin' was not declared in this scope
  112 |         for (auto& [k, _] : tg_count) {
      |                             ^~~~~~~~
lang.cpp:112:29: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:114:37: note:   'std::begin'
  114 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
      |                                     ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   'std::ranges::__cust::begin'
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note:   'std::ranges::__cust_access::begin'
  984 |     void begin(const auto&) = delete;
      |          ^~~~~
lang.cpp:112:29: error: 'end' was not declared in this scope
  112 |         for (auto& [k, _] : tg_count) {
      |                             ^~~~~~~~
lang.cpp:112:29: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:116:37: note:   'std::end'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   'std::ranges::__cust::end'
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   'std::ranges::__cust_access::end'
  137 |     void end(const auto&) = delete;
      |          ^~~
lang.cpp:113:32: error: request for member 'find' in 'freq3[l]', which is of non-class type 'int'
  113 |             auto it = freq3[l].find(k);
      |                                ^~~~
lang.cpp:114:32: error: request for member 'end' in 'freq3[l]', which is of non-class type 'int'
  114 |             if (it != freq3[l].end()) score += W3 * log(1.0 + it->second);
      |                                ^~~
lang.cpp:118:29: error: 'begin' was not declared in this scope
  118 |         for (auto& [k, _] : fg_count) {
      |                             ^~~~~~~~
lang.cpp:118:29: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:114:37: note:   'std::begin'
  114 |   template<typename _Tp> const _Tp* begin(const valarray<_Tp>&) noexcept;
      |                                     ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   'std::ranges::__cust::begin'
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note:   'std::ranges::__cust_access::begin'
  984 |     void begin(const auto&) = delete;
      |          ^~~~~
lang.cpp:118:29: error: 'end' was not declared in this scope
  118 |         for (auto& [k, _] : fg_count) {
      |                             ^~~~~~~~
lang.cpp:118:29: note: suggested alternatives:
/usr/include/c++/13/bits/range_access.h:116:37: note:   'std::end'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   'std::ranges::__cust::end'
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   'std::ranges::__cust_access::end'
  137 |     void end(const auto&) = delete;
      |          ^~~
lang.cpp:119:32: error: request for member 'find' in 'freq4[l]', which is of non-class type 'int'
  119 |             auto it = freq4[l].find(k);
      |                                ^~~~
lang.cpp:120:32: error: request for member 'end' in 'freq4[l]', which is of non-class type 'int'
  120 |             if (it != freq4[l].end()) score += W4 * log(1.0 + it->second);
      |                                ^~~
lang.cpp:139:9: error: 'uint64_t' was not declared in this scope
  139 |         uint64_t k = (uint64_t)E[i] * 65536ULL + E[i+1];
      |         ^~~~~~~~
lang.cpp:139:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:140:24: error: 'k' was not declared in this scope
  140 |         freq2[correct][k]++;
      |                        ^
lang.cpp:144:9: error: 'uint64_t' was not declared in this scope
  144 |         uint64_t k = (uint64_t)E[i] * (65536ULL*65536ULL)
      |         ^~~~~~~~
lang.cpp:144:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:147:24: error: 'k' was not declared in this scope
  147 |         freq3[correct][k]++;
      |                        ^
lang.cpp:151:9: error: 'uint64_t' was not declared in this scope
  151 |         uint64_t k = (uint64_t)E[i]   * (65536ULL*65536ULL*65536ULL)
      |         ^~~~~~~~
lang.cpp:151:9: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
lang.cpp:155:24: error: 'k' was not declared in this scope
  155 |         freq4[correct][k]++;
      |                        ^