#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <windows.h>
//mrChest's code

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define nl '\n'
#define oo 1e18
#define it iterator
#define py cout << "YES\n"
#define pn cout << "NO\n"

typedef long double ld;
typedef int64_t int64;
typedef uint64_t uint64;
typedef uint32_t uint;
typedef uint8_t uint8;

using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(time(0));

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using ordered_multiset = tree <T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using pri_que = priority_queue <T, vector <T>, greater <T>>;

/*мои дефайны, которые не влезли в сообщение*/

#define int int64

vector <int> toVec(int x, int k = 10){
    vector <int> v;
    while (x > 0){
        v.pb(x % k);
        x /= k;
    }
    return v;
}

int mp0[300007], mp1[300023], mp2[300043],
    w0[100000], w1[100000], w2[100000],
    cntW, pr[100000][8];

main() {
    if (fopen("fairphoto.in", "r")){
        freopen("fairphoto.in", "r", stdin);
        freopen("fairphoto.out", "w", stdout);
    }
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
                iostream::sync_with_stdio(0);
    int n,k;
    cin >> n >> k;
    pair <int,int> *a = new pair <int,int>[n];
    _in(a, n);
    sort(a, a + n);
    a = _map(a, n, [](pair <int,int> a){
            return pair <int,int>{a.f, a.s - 1};
        });

    pr[0][a[0].s]++;
    for (int i = 1; i < n; i++){
        for (int j = 0; j < 8; j++)
            pr[i][j] = pr[i - 1][j];
        pr[i][a[i].s]++;
    }


    int p0[8], p1[8], p2[8], num[8];

    p0[0] = 1;
    for (int i = 1; i < 8; i++)
        p0[i] = (p0[i - 1] * 200009) % 300007;
    p1[0] = 200009;
    for (int i = 1; i < 8; i++)
        p1[i] = (p1[i - 1] * 300007) % 300023;
    p2[0] = 300007;
    for (int i = 1; i < 8; i++)
        p2[i] = (p2[i - 1] * 300023) % 300043;

    fill(mp0, mp0 + 300007, oo);
    fill(mp1, mp1 + 300023, oo);
    fill(mp2, mp2 + 300043, oo);

    int ans = -1;
    for (int msk = 1; msk < (1 << 8); msk++){
        int bitsCnt = __builtin_popcount(msk);
        if (bitsCnt < k)
            continue;

        vector <int> v;
        for (int j = 0; j < 8; j++)
            if (msk & (1 << j)){
                num[j] = v.size();
                v.pb(j);
            }
        int cnt[v.size()];
        fill(cnt, cnt + v.size(), 0);

        for (int i = 0; i < n; i++){
            if ((msk & (1 << a[i].s)) == 0){
                for (int j = 0; j < cntW; j++)
                    mp0[w0[j]] = oo;
                for (int j = 0; j < cntW; j++)
                    mp1[w1[j]] = oo;
                for (int j = 0; j < cntW; j++)
                    mp2[w2[j]] = oo;
                cntW = 0;
                mp0[0] = i;
                mp1[0] = i;
                mp2[0] = i;
                fill(cnt, cnt + v.size(), 0);
                continue;
            }
            int k0 = 0, k1 = 0, k2 = 0;
            for (int i = 0; i < v.size() - 1; i++){
                k0 = (k0 + p0[i] * (cnt[i + 1] - cnt[i])) % 300007;
                k1 = (k1 + p1[i] * (cnt[i + 1] - cnt[i])) % 300023;
                k2 = (k2 + p2[i] * (cnt[i + 1] - cnt[i])) % 300043;
            }
            k0 = (k0 + 300007) % 300007;
            k1 = (k1 + 300023) % 300023;
            k2 = (k2 + 300043) % 300043;
            mp0[k0] = min(mp0[k0], i);
            mp1[k1] = min(mp1[k1], i);
            mp2[k2] = min(mp2[k2], i);
            w0[cntW] = k0;
            w1[cntW] = k1;
            w2[cntW] = k2;
            cntW++;
            cnt[num[a[i].s]]++;
            k0 = k1 = k2 = 0;
            for (int i = 0; i < v.size() - 1; i++){
                k0 += p0[i] * (cnt[i + 1] - cnt[i]);
                k1 += p1[i] * (cnt[i + 1] - cnt[i]);
                k2 += p2[i] * (cnt[i + 1] - cnt[i]);
            }
            k0 = (k0 % 300007 + 300007) % 300007;
            k1 = (k1 % 300023 + 300023) % 300023;
            k2 = (k2 % 300043 + 300043) % 300043;
            int t = max({mp0[k0], mp1[k1], mp2[k2]});
            if (t == oo)
                continue;
            int k = a[i].f - a[t].f;
            if (k > ans && (i - t + 1) % bitsCnt == 0){
                bool ok = 1;
                for (int j = 0; j < 8 && ok; j++)
                    if (msk & (1 << j))
                        if (pr[i][j] - (t > 0 ? pr[t - 1][j] : 0) != (i - t + 1) / bitsCnt)
                            ok = 0;
                if (ok)
                    ans = k;
            }
        }
        for (int j = 0; j < cntW; j++)
            mp0[w0[j]] = oo;
        for (int j = 0; j < cntW; j++)
            mp1[w1[j]] = oo;
        for (int j = 0; j < cntW; j++)
            mp2[w2[j]] = oo;
        cntW = 0;
    }
    cout << ans;
}

/*
999999937
999999929
999999893
999999883
999999797
999999761
999999757
999999751
999999739
999999733
300109
300089
300073
300043
300023
300007
200009
*/

USACO 14 Apr


G1: прикольная задачка, придумал даже почти сам. Проблема только в хешах. Много хешей не проходит по времени, а мало дают коллизии. Пока не знаю как оптимизировать. Удивился что Миша сдал с первой попытки, это большое везение. 

Я писал свою хеш-таблицу, потому что ни в gp_hash_table, ни в unorderd_map нельзя поставить дефолтные значения  

И вроде как логично, что своя, написанная под конкретные нужды и для них соптимизированная лучше, но почему-то TL или WA. 

И поэтому я думаю, что с таким же размером хеш-таблицы может пройти только по 2 причинам: более равномерная хеш-функция, и везение, что она не заколлизилась.
Буду рад услышать предложения. Если что, код вот: 

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

const int N = 200009;

vector < ll > p;
ll n, k, a[N], b[N], lst[N], pw[10], w[10];

ll get_hash() {
	ll res = 0;
	for (int i = 0; i < (int)p.size() - 1; i++) res += pw[i] * (w[p[i]] - w[p[i + 1]] + (ll)100001);
	return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("fairphoto.in", "r", stdin);
    freopen("fairphoto.out", "w", stdout);
    
    cin >> n >> k;
    
    vector < array < ll , 2 > > vec;
    
    for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		vec.push_back({x, --y});
    }
    
    sort(vec.begin(), vec.end());
    
    for (int i = 1; i <= n; i++) {
		a[i] = vec[i - 1][0];
		b[i] = vec[i - 1][1];
    }
    
    pw[0] = 1;
    for (int i = 1; i < 10; i++) pw[i] = pw[i - 1] * (ll)200003; 
    
    ll res = -1, cnt[8] = {}, crr = 0, j = 1;
    
    for (int i = 1; i <= n; i++) {
		if (!cnt[b[i]]) crr++;
		cnt[b[i]]++;
		
		while (crr >= k) {
			if (cnt[b[j]] == 1) crr--;
			cnt[b[j]]--;
			j++;
		}
		
		lst[i] = j - 1;
    }
    
    for (int mask = 0; mask < 256; mask++) {
		p.clear();
		for (int i = 0; i < 8; i++) if (mask & (1 << i)) p.push_back(i);
		
		if ((int)p.size() < k) continue;
		
		int l = 1, m = (int)p.size();
		
		while (l <= n) {
			if (!(mask & (1 << b[l]))) l++;
			else {
				int r = l;
				while (r < n && (mask & (1 << b[r + 1]))) r++;
				
				gp_hash_table < ll , ll > f;
				
				for (int i = 0; i < 8; i++) w[i] = 0;
				
				f[get_hash()] = l;
				
				for (int i = l; i <= r; i++) {
					w[b[i]]++;
					ll x = get_hash();
					if (f[x] != 0) {
						ll idx = f[x];
						if (idx <= lst[i]) res = max(res, a[i] - a[idx]);
					}
					else f[x] = i + 1;
				}
				
				l = r + 1;
			}
		}
    }
    
    cout << (res > 0 ? res : -1);
}

Здравствуйте, Михаил Семёнович. Пытался отписаться в форуме, но почему-то не отправилось сообщение. 

Тест	Результат	Время	Комментарий
1	33		0,1	верный ответ 	 
2	33		0,1	верный ответ 	 
3	33		0,1	верный ответ 	 
4	33		1,0	верный ответ 	 
5	33		0,5	верный ответ 	 
6	33		0,9	верный ответ 	 
7	0		2,0	снято по времени

Тест	Результат	Время	Комментарий
1	33		0,1	верный ответ 	 
2	33		0,1	верный ответ 	 
3	33		0,1	верный ответ 	 
4	33		0,3	верный ответ 	 
5	33		0,6	верный ответ 	 
6	33		1,4	верный ответ 	 
7	0		2,0	снято по времени

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <windows.h>
//mrChest's code

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC poison

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define nl '\n'
#define oo 1e18
#define it iterator
#define py cout << "YES\n"
#define pn cout << "NO\n"

typedef long double ld;
typedef int64_t int64;
typedef uint64_t uint64;
typedef uint32_t uint;
typedef uint8_t uint8;

using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(time(0));

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using ordered_multiset = tree <T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using pri_que = priority_queue <T, vector <T>, greater <T>>;

template <class T>
ostream& operator<< (ostream &out, set <T> st){
    out << '{';
    auto it = st.begin();
    while (it != st.end()){
        if (it != st.begin())
            out << ", ";
        out << (*(it++));
    }
    out << '}';
    return out;
}
template <class T>
ostream& operator<< (ostream &out, ordered_set <T> st){
    out << '{';
    auto it = st.begin();
    while (it != st.end()){
        if (it != st.begin())
            out << ", ";
        out << (*(it++));
    }
    out << '}';
    return out;
}
template <class A, class B>
istream& operator>> (istream &in, pair <A,B> &p){
    in >> p.f >> p.s;
    return in;
}
template <class T>
istream& operator>> (istream &in, vector <T> &v){
    for (auto &u : v)
        in >> u;
    return in;
}
template <class T>
void unsort(T b, T e){
    sort(b,e);
    reverse(b,e);
}
template <class T>
void _in(T *a, uint32_t n){
    for (uint32_t i = 0; i < n; i++)
        cin >> *(a + i);
}
template <class T>
void _out(T *a,uint32_t n){
    for (uint32_t i = 0; i < n; i++)
        cout << *(a + i) << " ";
    cout << nl;
}
template <class A, class B>
pair <A,B>& operator++ (pair <A,B> &x){
    x.f++;
    x.s++;
    return x;
}
template <class A, class B>
pair <A,B>& operator++ (pair <A,B> &x, int _){
    pair <A,B> ans = x;
    x.f++;
    x.s++;
    return ans;
}
template <class A, class B>
pair <A,B>& operator-- (pair <A,B> &x){
    x.f--;
    x.s--;
    return x;
}
template <class A, class B>
pair <A,B>& operator-- (pair <A,B> &x, int _){
    pair <A,B> ans = x;
    x.f--;
    x.s--;
    return ans;
}
int64 max(int a, int64 b){
    return (a > b ? a : b);
}
int64 max(int64 a, int b){
    return (a > b ? a : b);
}
int64 min(int a, int64 b){
    return (a < b ? a : b);
}
int64 min(int64 a, int b){
    return (a < b ? a : b);
}

template <class T>
vector <T> toVec(T *a, uint32_t n){
    vector <T> ans(n);
    for (uint32_t i = 0; i < n; i++)
        ans[i] = a[i];
    return ans;
}

template <class T>
T max(vector <T> v){
    assert(v.size() > 0);
    T ans = v[0];
    for (uint32_t i = 1; i < v.size(); i++)
        ans = max(ans, v[i]);
    return ans;
}
template <class T, class fun>
T max(vector <T> v, fun comp){
    assert(v.size() > 0);
    T ans = v[0];
    for (uint32_t i = 1; i < v.size(); i++)
        ans = max(ans, v[i], comp);
    return ans;
}

template <class T>
T min(vector <T> v){
    assert(v.size() > 0);
    T ans = v[0];
    for (uint32_t i = 1; i < v.size(); i++)
        ans = min(ans, v[i]);
    return ans;
}
template <class T, class fun>
T min(vector <T> v, fun comp){
    assert(v.size() > 0);
    T ans = v[0];
    for (uint32_t i = 1; i < v.size(); i++)
        ans = min(ans, v[i], comp);
    return ans;
}

template <class T>
T sum(vector <T> v){
    assert(v.size() > 0);
    T ans = v[0];
    for (uint32_t i = 1; i < v.size(); i++)
        ans += v[i];
    return ans;
}

template <class T, class fun>
vector <T> _map(vector <T> v, fun f){
    vector <T> ans(v.size());
    for (uint32_t i = 0; i < v.size(); i++)
        ans[i] = f(v[i]);
    return ans;
}

int pr[100001][8], W, t, f;
uint64 w[100001];

main() {
    if (fopen("fairphoto.in", "r")){
        freopen("fairphoto.in", "r", stdin);
        freopen("fairphoto.out", "w", stdout);
    }
    cin.tie(0); ios_base::sync_with_stdio(0); cout.tie(0);
                iostream::sync_with_stdio(0);
    int n,k;
    cin >> n >> k;
    pair <int,int> *a = new pair <int,int>[n + 1];
    for (int i = 1; i <= n; i++){
        cin >> a[i].f >> a[i].s;
                         a[i].s--;
    }
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 8; j++)
            pr[i][j] = pr[i - 1][j];
        pr[i][a[i].s]++;
    }


    uint64 p[8];
    int num[8];
    p[0] = 1;
    for (int i = 1; i < 8; i++)
        p[i] = p[i - 1] * 999999733ULL;


    int ans = -1;
    for (int msk = 1; msk < (1 << 8); msk++){
        int cntBits = 0;
        for (int j = 0; j < 8; j++)
            if (msk & (1 << j))
                num[j] = cntBits++;

        if (cntBits < k)
            continue;

        gp_hash_table <uint64, int> mp;

        uint64 k = 0;

        for (int i = 1; i <= n; i++){
            if ((msk & (1 << a[i].s)) == 0){
                for (int j = 0; j < W; j++)
                    mp[w[j]] = 0;
                W = 0;
                continue;
            }

            if (mp[k] == 0){
                mp[k] = i;
                w[W] = k;
                W++;
            }

            if (num[a[i].s] > 0)
                k += p[num[a[i].s] - 1];
            if (num[a[i].s] < cntBits - 1)
                k -= p[num[a[i].s]];

            t = mp[k];
            if (t == 0)
                continue;
            f = a[i].f - a[t].f;
            if (f > ans && (i - t + 1) % cntBits == 0)
                ans = f;
        }
    }
    cout << ans;
}

USACO 14 Dec +6

А это банальный человеческий фактор. Не знаю, что делать чтобы это не повторилось. Это такая ошибка, которую в первый раз допустишь, во второй нет. Когда я буду писать другую задачу, тоже могу забыть про это ограничение, но обычно я довольно внимателен к это и такие ошибки у меня крайняя редкость.
 

Давай для начала прочитай, что Миша писал по лишним отсылкам в олимпиадах этого лета.

Выпиши – скопируй все его выводы – советы себе.
Удали, которые тебе не полезны, не нравятся.
Останутся полезные советы от хорошего олимпиадника.
 

Михаил Семёнович, я не знаю, какие из этого следуют выводы и как с этим бороться. Я просто не знаю??.
Может вы подскажите, что делать, чтобы такое не повторялось?
 

1. С тех пор, как в контестах появилась task.cfg
просто условия стали понятнее (кстати, в них исчезли непонятки, когда уточнений в условии нет, и их приходиться искать в тестах)).
 

3) перед посылкой убедится что решение нормальное и написано верно  

может даже, перед отправкой делать свои тесты