Submission #1186407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186407		Tymond	Seats (IOI18_seats)	C++20	11 / 100	4093 ms	44192 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int INF = 1e9;
const int MAXN =  1e6 + 7;
const int B = 800;
vector<pii> pos;
vector<vi> A;
int h, w, ans;
pii cnt[MAXN];//.fi - ile trójek z dużymi elementami, .se - ile trójek z małymi elementami
pii changeB[MAXN / B + 10];
unordered_map<pii, int, pair_hash> cntB[MAXN / B + 10];
const pii correct = mp(4, 0);

void operator+=(pii& a, const pii& b){
    a.fi += b.fi;
    a.se += b.se;
}

pii operator+(const pii& a, const pii& b){
    return mp(a.fi + b.fi, a.se + b.se);
}

pii operator-(const pii& a, const pii& b){
    return mp(a.fi - b.fi, a.se - b.se);
}

int isOk(int x){
    if(cnt[x] + changeB[x / B] == correct){
        return 1;
    }
    return 0;
}

int cntOk(int b){
    if(cntB[b].find(correct - changeB[b]) == cntB[b].end()){
        return 0;
    }
    return cntB[b][correct - changeB[b]];
}

void upd(int l, int p, pii x){
    p = min(p, h * w);
    if(l > p){
        return;
    }
    
    //cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
   while(l <= p && l % B != 0){
        ans -= isOk(l);
        cnt[l] += x;
        ans += isOk(l);
        l++;
    }
    //cerr << l << ' ' << ans << '\n';
   // cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
    while(l + B - 1 <= p){
       // cerr << l << '\n';
        ans -= cntOk(l / B);
        changeB[l / B] += x;
       /// cerr << l << '\n';
        ans += cntOk(l / B);
        l += B;
       // cerr << l << '\n';
    }
   // cerr << l << ' ' << ans << '\n';
   // cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
   //cerr << cnt[2] + changeB[2 / B] << '\n';
    while(l <= p){
        ans -= isOk(l);
        cnt[l] += x;
        ans += isOk(l);
        l++;
    }
   // cerr << l << ' ' << ans << '\n';
}

void change(int x, int y, int val=1){
   // cerr << "NIGGA1\n";
    vi curr = {A[x][y], A[x + 1][y], A[x][y + 1], A[x + 1][y + 1]};
    sort(all(curr));
   // cerr << "NIGGA2\n";
    upd(curr[0], curr[1] - 1, mp(val, 0));
    //cerr << "NIGGA3\n";
    upd(curr[2], curr[3] - 1, mp(0, val));
    //cerr << "NIGGA3\n";
}

void give_initial_chart(int H, int W, vi R, vi C){
    h = H;
    w = W;
    pos.resize(h * w + 1);
    A.resize(h + 2, vi(w + 2, INF));
    for(int i = 1; i <= h * w; i++){
        pos[i] = mp(R[i - 1] + 1, C[i - 1] + 1);
        A[R[i - 1] + 1][C[i - 1] + 1] = i;
    }
   // cerr << "NIGGA\n";
    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            change(i, j);
        }
    }
    //cerr << "NIGGA\n";
    ans = 0;
    for(int i = 1; i <= h * w; i++){
        cnt[i] += changeB[i / B];
        if(cnt[i] == correct){
            ans++;
        }
        cntB[i / B][cnt[i]]++;
        //cerr << i / B << ' ' << cnt[i] << '\n';
    }
    
    for(int i = 0; i <= h * w; i++){
        changeB[i / B] = mp(0, 0);
    }
    //cerr << ans << '\n';
   //cerr << "NIGGA\n";
}

//zamień miejsca liczb a i b
//potem zwróć wynik po zamianie
int swap_seats(int a, int b) {
    a++;
    b++;
    int p[2] = {a, b};
    //cerr << pos[a] << ' ' << pos[b] << '\n';
    for(int j = 0; j < 2; j++){
        for(int x = pos[p[j]].fi - 1; x <= pos[p[j]].fi; x++){
            for(int y = pos[p[j]].se - 1; y <= pos[p[j]].se; y++){
                change(x, y, -1);
            }
        }
    }
    //cerr << "NIGGA\n";
    swap(pos[p[0]], pos[p[1]]);
    swap(A[pos[p[0]].fi][pos[p[0]].se], A[pos[p[1]].fi][pos[p[1]].se]);
    for(int j = 0; j < 2; j++){
        for(int x = pos[p[j]].fi - 1; x <= pos[p[j]].fi; x++){
            for(int y = pos[p[j]].se - 1; y <= pos[p[j]].se; y++){
                change(x, y);
            }
        }
    }
    ans = 0;
    for(int i = 1; i <= h * w; i++){
        if(cnt[i] + changeB[i / B] == correct){
            ans++;
        }
    }
    //cerr << "NIGGA\n";
    return ans;
}

/*int main(){
    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    
    cout << swap_seats(0, 5) << '\n';
    cout << swap_seats(0, 5) << '\n';

    return 0;
}*/

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30