Submission #56781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56781	2018-07-12T14:50:13 Z	Benq	Languages (IOI10_languages)	C++14	0 / 100	10000 ms	13072 KB

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"
 
// int language(int x) { cout << x << "\n"; return 0; }

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;
    }
};

contain m[56][3], tmp[3];
 
double common(int x) {
    double ret = 0;
    F0R(i,3) {
        ret += pow(2,i)*tmp[i].common(m[x][i]);
        // if (x == 0) cout << "OOPS " << tmp[i].common(m[x][i]) << "\n";
    }
    // if (x == 0) cout << ret << "\n";
    return ret;
}

void excerpt(int *E) {
    pair<double,int> bes = {-MOD,0};
    F0R(i,3) tmp[i].clear();
    
    F0R(i,3) 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,3) F0R(j,100-i)  {
        vi v;
        F0R(k,i+1) v.pb(E[j+k]); 
        m[x][i].ins(v);
    }
}

/*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() {
    int* t = con("Water scarcity is the lack of fresh water resources to meet water demand. It affects every continent and was listed in 2015 by the World Economic Forum as the largest global risk in terms of potential impact over the next decade.");
    int* T = con("hysical water scarcity results from inadequate natural water resources to supply a region's demand, and economic water scarcity results from poor management of the sufficient available water resources. According to the United Nations Development Programme, the latter is found more often to be the cause of countries or regions experiencing water scarcity, as most countries or regions have enough water to meet household, industrial, agricultural, and environmental needs,");
    excerpt(t);
    excerpt(T);
}*/

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10031 ms	13072 KB	Time limit exceeded

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10014 ms	12744 KB	Time limit exceeded