Submission #56795

#	Time	Username	Problem	Language	Result	Execution time	Memory
56795		Benq	Languages (IOI10_languages)	C++14	82 / 100	3791 ms	1232 KiB

lang

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
#include "grader.h"
#include "lang.h"
 
#define L 2

// int language(int x) { return rand() % 56; }

ll hsh(vi v) {
    ll mul = 1, sum = 0;
    F0R(i,sz(v)) {
        sum += v[i]*mul;
        mul *= 65536;
    }
    return sum;
}

struct contain {
    unordered_map<ll,int> u;
    int tot = 0;
    
    void clear() {
        u.clear();
        tot = 0;
    }
    
    void ins(vi v) { u[hsh(v)] ++; tot ++; }
    
    double get(ll x) {
        if (!u.count(x)) return 0;
        return (double)u[x]/tot;
    }
    
    double common(contain& c) {
        if (c.tot == 0) return -MOD;
        double same = 0;
        for (auto a: u) {
            //cout << "HI " << a.f << " " << a.s << " " << get(a.f) << "\n";
            same += min(get(a.f),c.get(a.f));
        }
        return same;
    }
    
    void clean() {
        vi del;
        for (auto a: u) if ((double)a.s/tot < 1.0/500) del.pb(a.f);
        for (auto a: del) u.erase(a);
    }
    
    void merge(contain& c) {
        c.tot += tot;
        for (auto a: u) c.u[a.f] += a.s;
        c.clean();
        clear();
    }
};

contain m[56][L], tmp[L];
 
double common(int x) {
    double ret = 0;
    F0R(i,L) {
        ret += pow(2,i)*tmp[i].common(m[x][i]);
    }
    return ret;
}

void excerpt(int *E) {
    pair<double,int> bes = {-MOD,0};
    F0R(i,L) tmp[i].clear();
    
    F0R(i,L) F0R(j,100-i)  {
        vi v;
        F0R(k,i+1) v.pb(E[j+k]); 
        tmp[i].ins(v);
    }
    
    F0R(i,56) bes = max(bes,{common(i),i});
    
    int x = language(bes.s);
    F0R(i,L) tmp[i].merge(m[x][i]);
}

/*int* con(string s) {
    s = s.substr(0,100);
    assert(sz(s) == 100);
    int* z = new int[100];
    F0R(i,100) z[i] = s[i];
    return z;
}

int main() {
    F0R(i,3000) {
        int* t = new int[100];
        F0R(j,100) t[j] = rand() % 65536;
        excerpt(t);
    }
}*/

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