| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 699890 | qwerasdfzxcl | Languages (IOI10_languages) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
constexpr ll DIG = 1e5, B = 57;
bool st[101][100100];
bool st2[101][100100];
bool st22[101][100100];
bool st3[101][100100];
bool st32[101][100100];
bool st4[101][100100];
bool st42[101][100100];
bool st5[101][100100];
bool st52[101][100100];
bool st6[101][100100];
bool st62[101][100100];
int fail[101][101], iter, cnt[101];
unordered_set<int> S[100100];
int T[100100];
unsigned short myHash(ull x){
return (unsigned short)(x ^ x>>11 ^ x>>22 ^ x>>33 ^ x>>44 ^ x>>55);
}
unsigned short myHash2(ull x){
return (unsigned short)(x ^ x>>13 ^ x>>26 ^ x>>39 ^ x>>52);
}
void push(int *E, int typ){
for (int i=0;i<100;i++){
S[E[i]].insert(typ);
T[E[i]]++;
}
for (int i=0;i<100;i++) st[typ][E[i]] = 1;
for (int i=0;i<99;i++){
st2[typ][myHash(E[i]<<16 | E[i+1])] = 1;
st22[typ][myHash2(E[i]<<16 | E[i+1])] = 1;
}
for (int i=0;i<98;i++){
st3[typ][myHash((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2])] = 1;
st32[typ][myHash2((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2])] = 1;
}
for (int i=0;i<97;i++){
st4[typ][myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]))] = 1;
st42[typ][myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]))] = 1;
}
for (int i=0;i<96;i++){
auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]);
auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]);
st5[typ][x] = 1;
st52[typ][y] = 1;
}
for (int i=0;i<95;i++){
auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]<<16 | E[i+5]);
auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]<<16 | E[i+5]);
st6[typ][x] = 1;
st62[typ][y] = 1;
}
//for (int i=0;i<96;i++) st5[typ].insert((ull)E[i]<<50 ^ (ull)E[i+1]<<40 ^ (ull)E[i+2]<<30 ^ (ull)E[i+3]<<20 ^ (ull)E[i+4]<<10);
}
int calc(int *E, int typ){
int ret = 0;
for (int i=0;i<100;i++){
if (!st[typ][E[i]]) ret++;
if (S[E[i]].size()==1 && *S[E[i]].begin() == typ && T[E[i]] >= 5) ret -= 10;
}
for (int i=0;i<99;i++){
auto x = (E[i]<<16 | E[i+1]);
if (!st2[typ][myHash(x)] || !st22[typ][myHash2(x)]) ret++;
}
for (int i=0;i<98;i++){
auto x = ((ull)E[i]<<32 | (ull)E[i+1]<<16 | E[i+2]);
if (!st3[typ][myHash(x)] || !st32[typ][myHash2(x)]) ret++;
}
for (int i=0;i<97;i++){
auto x = ((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3]);
if (!st4[typ][myHash(x)] || !st42[typ][myHash2(x)]) ret++;
}
for (int i=0;i<96;i++){
auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]);
auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]);
if (!st5[typ][x] || !st52[typ][y]) ret++;
}
for (int i=0;i<95;i++){
auto x = myHash(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash(E[i+4]<<16 | E[i+5]);
auto y = myHash2(((ull)E[i]<<48 | (ull)E[i+1]<<32 | (ull)E[i+2]<<16 | E[i+3])) ^ myHash2(E[i+4]<<16 | E[i+5]);
if (!st6[typ][x] || !st62[typ][y]) ret++;
}
return ret;
}
int X[101];
void excerpt(int *E, string I[]){
++iter;
int idx = -1;
for (int i=0;i<56;i++){
X[i] = calc(E, i);
}
idx = min_element(X, X+56) - X;
int L = language(idx);
//if (iter>=5000 && idx!=L) printf("%d / %d\n", calc(E, idx), calc(E, L));
push(E, L);
cnt[L]++;
fail[idx][L]++;
/*if (iter==580){
vector<pair<int, pair<int, int>>> V;
for (int i=0;i<56;i++){
for (int j=0;j<56;j++) if (i!=j){
V.emplace_back(fail[i][j], make_pair(i, j));
}
}
sort(V.begin(), V.end(), greater<pair<int, pair<int, int>>>());
for (int z=0;z<10;z++){
printf("fail %d(%s) (ans = %d(%s)): %d\n", V[z].second.first, I[V[z].second.first].c_str(), V[z].second.second, I[V[z].second.second].c_str(), V[z].first);
}
int val[100] = {0};
for (int i=0;i<65536;i++) if (S[i].size()==1 && T[i]>=6){
val[*S[i].begin()]++;
}
printf("%d %d %d\n", val[45], val[14], val[9]);
}*/
}