| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1186389 | Tymond | 자리 배치 (IOI18_seats) | C++20 | 0 ms | 0 KiB |
#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 = 1e3;
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, custom_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;
}*/