oj.uz

답안 #342637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342637 2021-01-02T14:11:28 Z AmineWeslati 자리 배치 (IOI18_seats) C++14
100 / 100
 1421 ms 130140 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 2e9;
const int MX = 1e6 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#ifndef LOCAL
#include "seats.h"
#endif

int H,W;
vi R(MX),C(MX);
V<vi> g;

bool grid(int i, int j){
	return i>=0 && j>=0 && i<H && j<W;
}

struct node{
	int nb=0,mn=INF,sum=0;
};
V<node> t(MX*4);
node combine(node a, node b){
	int nb,mn,sum=a.sum+b.sum;
	if(a.mn < a.sum+b.mn){
		mn=a.mn;
		nb=a.nb;
	}
	else if(a.mn > a.sum+b.mn){
		mn=a.sum+b.mn;
		nb=b.nb;
	}
	else{
		mn=a.mn;
		nb=a.nb+b.nb;
	}
	return {nb,mn,sum};
}
void upd(int i, int v, int pos=1, int tl=0, int tr=H*W-1){
	if(tl==tr){
		t[pos]={1,v,v};
		return;
	}
	int tm=(tl+tr)/2;
	if(i<=tm) upd(i,v,pos*2,tl,tm);
	else upd(i,v,pos*2+1,tm+1,tr);
	t[pos]=combine(t[pos*2],t[pos*2+1]);
}

int delta(int x, int y){
	if(g[x][y]==0) return 0;
	vi cnt(5,0);
	FOR(xx,0,2) FOR(yy,0,2){
		int nwx=x-xx, nwy=y-yy;
		int nb=0;
		if(grid(nwx,nwy) && g[nwx][nwy]<=g[x][y]) nb++; 
		if(grid(nwx+1,nwy) && g[nwx+1][nwy]<=g[x][y]) nb++; 
		if(grid(nwx,nwy+1) && g[nwx][nwy+1]<=g[x][y]) nb++; 
		if(grid(nwx+1,nwy+1) && g[nwx+1][nwy+1]<=g[x][y]) nb++; 
		cnt[nb]++;
	}
	return cnt[1]+cnt[3]-cnt[2]-cnt[4];
}

void give_initial_chart(int H, int W, vi R, vi C) {
	::H=H; ::W=W; ::R=R; ::C=C;
	g.resize(H);
	FOR(i,0,H) g[i].resize(W);
	FOR(i,0,sz(R)) g[R[i]][C[i]]=i;
	
	FOR(i,0,H*W) upd(i,delta(R[i],C[i]));
}	

int swap_seats(int a, int b) {
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	swap(g[R[a]][C[a]],g[R[b]][C[b]]);

	FOR(x,-1,2) FOR(y,-1,2){
		if(grid(R[a]+x,C[a]+y))
			upd(g[R[a]+x][C[a]+y],delta(R[a]+x,C[a]+y));
		if(grid(R[b]+x,C[b]+y))
			upd(g[R[b]+x][C[b]+y],delta(R[b]+x,C[b]+y));
	}
	return t[1].nb;
}

#ifdef LOCAL
int main() {
    boost; IO();

    int R,C; cin>>R>>C;
    vi x(R*C),y(R*C);
    FOR(i,0,R*C) cin>>x[i];
    FOR(i,0,R*C) cin>>y[i];
    give_initial_chart(R,C,x,y);
    cout << swap_seats(0,5) << endl;
    cout << swap_seats(0,5) << endl;


    return 0;
}
#endif

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55276 KB Output is correct
2 Correct 49 ms 55276 KB Output is correct
3 Correct 53 ms 55276 KB Output is correct
4 Correct 43 ms 55276 KB Output is correct
5 Correct 42 ms 55276 KB Output is correct
6 Correct 50 ms 55276 KB Output is correct
7 Correct 51 ms 55276 KB Output is correct
8 Correct 52 ms 55296 KB Output is correct
9 Correct 51 ms 55276 KB Output is correct
10 Correct 51 ms 55404 KB Output is correct
11 Correct 49 ms 55276 KB Output is correct
12 Correct 42 ms 55276 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55276 KB Output is correct
2 Correct 49 ms 55276 KB Output is correct
3 Correct 53 ms 55276 KB Output is correct
4 Correct 43 ms 55276 KB Output is correct
5 Correct 42 ms 55276 KB Output is correct
6 Correct 50 ms 55276 KB Output is correct
7 Correct 51 ms 55276 KB Output is correct
8 Correct 52 ms 55296 KB Output is correct
9 Correct 51 ms 55276 KB Output is correct
10 Correct 51 ms 55404 KB Output is correct
11 Correct 49 ms 55276 KB Output is correct
12 Correct 42 ms 55276 KB Output is correct
13 Correct 72 ms 55532 KB Output is correct
14 Correct 75 ms 55660 KB Output is correct
15 Correct 60 ms 55660 KB Output is correct
16 Correct 51 ms 56044 KB Output is correct
17 Correct 60 ms 55660 KB Output is correct
18 Correct 67 ms 55544 KB Output is correct
19 Correct 66 ms 55660 KB Output is correct
20 Correct 59 ms 55788 KB Output is correct
21 Correct 51 ms 55660 KB Output is correct
22 Correct 51 ms 56044 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 886 ms 90776 KB Output is correct
2 Correct 716 ms 90732 KB Output is correct
3 Correct 690 ms 90732 KB Output is correct
4 Correct 693 ms 90792 KB Output is correct
5 Correct 711 ms 90860 KB Output is correct
6 Correct 689 ms 90824 KB Output is correct
7 Correct 689 ms 90860 KB Output is correct
8 Correct 701 ms 90732 KB Output is correct
9 Correct 692 ms 90732 KB Output is correct
10 Correct 691 ms 90732 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 55532 KB Output is correct
2 Correct 126 ms 58296 KB Output is correct
3 Correct 688 ms 79340 KB Output is correct
4 Correct 827 ms 79340 KB Output is correct
5 Correct 634 ms 79212 KB Output is correct
6 Correct 1083 ms 130140 KB Output is correct
7 Correct 674 ms 79340 KB Output is correct
8 Correct 695 ms 79444 KB Output is correct
9 Correct 695 ms 79836 KB Output is correct
10 Correct 712 ms 82444 KB Output is correct
11 Correct 698 ms 102876 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 56808 KB Output is correct
2 Correct 90 ms 56808 KB Output is correct
3 Correct 105 ms 56936 KB Output is correct
4 Correct 122 ms 56936 KB Output is correct
5 Correct 147 ms 57132 KB Output is correct
6 Correct 815 ms 91656 KB Output is correct
7 Correct 833 ms 91628 KB Output is correct
8 Correct 813 ms 91816 KB Output is correct
9 Correct 890 ms 91884 KB Output is correct
10 Correct 776 ms 91816 KB Output is correct
11 Correct 768 ms 91640 KB Output is correct
12 Correct 768 ms 91716 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55276 KB Output is correct
2 Correct 49 ms 55276 KB Output is correct
3 Correct 53 ms 55276 KB Output is correct
4 Correct 43 ms 55276 KB Output is correct
5 Correct 42 ms 55276 KB Output is correct
6 Correct 50 ms 55276 KB Output is correct
7 Correct 51 ms 55276 KB Output is correct
8 Correct 52 ms 55296 KB Output is correct
9 Correct 51 ms 55276 KB Output is correct
10 Correct 51 ms 55404 KB Output is correct
11 Correct 49 ms 55276 KB Output is correct
12 Correct 42 ms 55276 KB Output is correct
13 Correct 72 ms 55532 KB Output is correct
14 Correct 75 ms 55660 KB Output is correct
15 Correct 60 ms 55660 KB Output is correct
16 Correct 51 ms 56044 KB Output is correct
17 Correct 60 ms 55660 KB Output is correct
18 Correct 67 ms 55544 KB Output is correct
19 Correct 66 ms 55660 KB Output is correct
20 Correct 59 ms 55788 KB Output is correct
21 Correct 51 ms 55660 KB Output is correct
22 Correct 51 ms 56044 KB Output is correct
23 Correct 886 ms 90776 KB Output is correct
24 Correct 716 ms 90732 KB Output is correct
25 Correct 690 ms 90732 KB Output is correct
26 Correct 693 ms 90792 KB Output is correct
27 Correct 711 ms 90860 KB Output is correct
28 Correct 689 ms 90824 KB Output is correct
29 Correct 689 ms 90860 KB Output is correct
30 Correct 701 ms 90732 KB Output is correct
31 Correct 692 ms 90732 KB Output is correct
32 Correct 691 ms 90732 KB Output is correct
33 Correct 69 ms 55532 KB Output is correct
34 Correct 126 ms 58296 KB Output is correct
35 Correct 688 ms 79340 KB Output is correct
36 Correct 827 ms 79340 KB Output is correct
37 Correct 634 ms 79212 KB Output is correct
38 Correct 1083 ms 130140 KB Output is correct
39 Correct 674 ms 79340 KB Output is correct
40 Correct 695 ms 79444 KB Output is correct
41 Correct 695 ms 79836 KB Output is correct
42 Correct 712 ms 82444 KB Output is correct
43 Correct 698 ms 102876 KB Output is correct
44 Correct 92 ms 56808 KB Output is correct
45 Correct 90 ms 56808 KB Output is correct
46 Correct 105 ms 56936 KB Output is correct
47 Correct 122 ms 56936 KB Output is correct
48 Correct 147 ms 57132 KB Output is correct
49 Correct 815 ms 91656 KB Output is correct
50 Correct 833 ms 91628 KB Output is correct
51 Correct 813 ms 91816 KB Output is correct
52 Correct 890 ms 91884 KB Output is correct
53 Correct 776 ms 91816 KB Output is correct
54 Correct 768 ms 91640 KB Output is correct
55 Correct 768 ms 91716 KB Output is correct
56 Correct 125 ms 56848 KB Output is correct
57 Correct 206 ms 56940 KB Output is correct
58 Correct 320 ms 57132 KB Output is correct
59 Correct 1186 ms 91884 KB Output is correct
60 Correct 1399 ms 91772 KB Output is correct
61 Correct 1045 ms 91884 KB Output is correct
62 Correct 886 ms 91944 KB Output is correct
63 Correct 1207 ms 91816 KB Output is correct
64 Correct 1147 ms 92012 KB Output is correct
65 Correct 1056 ms 91884 KB Output is correct
66 Correct 1159 ms 92268 KB Output is correct
67 Correct 1117 ms 94956 KB Output is correct
68 Correct 980 ms 106092 KB Output is correct
69 Correct 1421 ms 115336 KB Output is correct