oj.uz

Submission #70376

# Submission time Handle Problem Language Result Execution time Memory
70376 2018-08-22T17:43:24 Z Benq Mini tetris (IOI16_tetris) C++14
100 / 100
 73 ms 2772 KB 
#include "tetris.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

typedef array<array<int,3>,4> mat;

set<int> adj[1<<12][3];
set<pi> radj[1<<12];
int cur = 0;
bool ok[1<<12];

void prin(mat gr) {
	F0Rd(i,4) {
		F0R(j,3) cout << gr[i][j];
		cout << "\n";
	}
	cout << "----\n";
}

mat decode(int x) {
    mat g;
    F0R(i,4) {
        F0R(j,3) if (x&(1<<(3*i+j))) g[i][j] = 1;
        else g[i][j] = 0;
    }
    return g;
}

void prin(int x) {
    if (x == -1) cout << "OOPS\n";
    else prin(decode(x));
}


void del(mat& gr) {
	F0Rd(i,4) {
	    bool ok = 1;
	    F0R(j,3) if (!gr[i][j]) {
	        ok = 0;
	        break;
	    }
	    if (!ok) continue;
		FOR(I,i,3) F0R(j,3) gr[I][j] = gr[I+1][j];
		F0R(j,3) gr[3][j] = 0;
	}
}

int encode(mat gr) {
	int ans = 0;
	F0R(i,4) F0R(j,3) if (gr[i][j]) {
		ans ^= (1<<(3*i+j));
	}
	return ans;
}

int nex(int a, vpi b) {
	mat gr; 
	array<int,3> mn = {MOD,MOD,MOD}, mx = {-1,-1,-1};

	F0R(i,4) F0R(j,3) {
		if (a&(1<<(3*i+j))) {
			gr[i][j] = 1;
			mx[j] = max(mx[j],i);
		} else gr[i][j] = 0;
	}

	int ad = -MOD;
	for (auto x: b) {
		if (x.s < 0 || x.s >= 3) return -1;
		mn[x.s] = min(mn[x.s],x.f);
	}
	F0R(i,3) ad = max(ad,mx[i]-mn[i]+1);
	for (auto& x: b) {
		x.f += ad;
		if (x.f >= 4) return -1;
		gr[x.f][x.s] = 1;
	}

	del(gr);
	return encode(gr);
}

vpi tmp[3];

vpi rot(vpi x) {
	// i,j -> -j,i 
	pi mn = {MOD,MOD};
	for (auto& a: x) {
		a = {a.s,-a.f};
		mn.f = min(mn.f,a.f);
		mn.s = min(mn.s,a.s);
	}
	for (auto& a: x) {
	    a.f -= mn.f, a.s -= mn.s;
	}
	return x;
}

vpi rot(vpi x, int d) {
	F0R(i,d) x = rot(x);
	return x;
}

vpi trans(vpi x, int d) {
	for (auto& a: x) a.s += d;
	return x;
}

void insEdge(int a, int b, int c) {
    if (c == -1) return;
    adj[a][b].insert(c);
    radj[c].insert({a,b});
}

void init(int n) {
	tmp[0] = {{0,0},{0,1},{0,2}};
	tmp[1] = {{0,0},{0,1}};
	tmp[2] = {{0,0},{1,0},{0,1}};

    queue<int> bad;
    
	F0R(i,1<<12) {
	    ok[i] = 1;
	    F0R(j,3) F0R(k,4) F0R(l,3) { // #, rotation, translation
    	    insEdge(i,j,nex(i,trans(rot(tmp[j],k),l)));
    	}
    	F0R(j,3) if (sz(adj[i][j]) == 0) {
    	    ok[i] = 0;
    	    // prin(i);
    	    bad.push(i);
    	    break;
    	}
	}
	while (sz(bad)) {
	    int x = bad.front(); bad.pop();
	    for (pi t: radj[x]) {
	        adj[t.f][t.s].erase(x);
	        if (sz(adj[t.f][t.s]) == 0 && ok[t.f]) {
	            ok[t.f] = 0;
	            bad.push(t.f);
	        }
	    }
	}
	assert(ok[1]);
}

int position;
int rotation;

void new_figure(int figure_type) {
    figure_type --;
	F0R(k,4) F0R(l,3) { // #, rotation, translation
		int CUR = nex(cur,trans(rot(tmp[figure_type],k),l));
		if (CUR != -1 && ok[CUR]) {
			position = l;
			rotation = k;
            //cout << position << " " << cur << " " << CUR << " " << rotation << "\n";
			cur = CUR;
			//prin(cur);
			return;
		}
	}
}

int get_position() {
	return position;
}

int get_rotation() {
	return rotation;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2040 KB Win!
2 Correct 53 ms 2040 KB Win!
3 Correct 40 ms 2232 KB Win!
4 Correct 42 ms 2320 KB Win!
5 Correct 44 ms 2320 KB Win!
6 Correct 44 ms 2320 KB Win!
7 Correct 48 ms 2392 KB Win!
8 Correct 48 ms 2396 KB Win!

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2396 KB Win!
2 Correct 73 ms 2396 KB Win!
3 Correct 51 ms 2396 KB Win!
4 Correct 46 ms 2424 KB Win!
5 Correct 46 ms 2424 KB Win!
6 Correct 46 ms 2444 KB Win!
7 Correct 45 ms 2448 KB Win!
8 Correct 54 ms 2452 KB Win!

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2040 KB Win!
2 Correct 53 ms 2040 KB Win!
3 Correct 40 ms 2232 KB Win!
4 Correct 42 ms 2320 KB Win!
5 Correct 44 ms 2320 KB Win!
6 Correct 44 ms 2320 KB Win!
7 Correct 48 ms 2392 KB Win!
8 Correct 48 ms 2396 KB Win!
9 Correct 43 ms 2396 KB Win!
10 Correct 73 ms 2396 KB Win!
11 Correct 51 ms 2396 KB Win!
12 Correct 46 ms 2424 KB Win!
13 Correct 46 ms 2424 KB Win!
14 Correct 46 ms 2444 KB Win!
15 Correct 45 ms 2448 KB Win!
16 Correct 54 ms 2452 KB Win!
17 Correct 57 ms 2492 KB Win!
18 Correct 38 ms 2492 KB Win!
19 Correct 44 ms 2492 KB Win!
20 Correct 66 ms 2492 KB Win!
21 Correct 46 ms 2600 KB Win!
22 Correct 46 ms 2600 KB Win!
23 Correct 46 ms 2600 KB Win!
24 Correct 49 ms 2600 KB Win!
25 Correct 46 ms 2600 KB Win!
26 Correct 47 ms 2600 KB Win!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2628 KB Win!
2 Correct 45 ms 2628 KB Win!
3 Correct 51 ms 2628 KB Win!
4 Correct 50 ms 2628 KB Win!
5 Correct 45 ms 2628 KB Win!
6 Correct 45 ms 2628 KB Win!
7 Correct 51 ms 2628 KB Win!
8 Correct 51 ms 2628 KB Win!

Subtask #5
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2040 KB Win!
2 Correct 53 ms 2040 KB Win!
3 Correct 40 ms 2232 KB Win!
4 Correct 42 ms 2320 KB Win!
5 Correct 44 ms 2320 KB Win!
6 Correct 44 ms 2320 KB Win!
7 Correct 48 ms 2392 KB Win!
8 Correct 48 ms 2396 KB Win!
9 Correct 43 ms 2396 KB Win!
10 Correct 73 ms 2396 KB Win!
11 Correct 51 ms 2396 KB Win!
12 Correct 46 ms 2424 KB Win!
13 Correct 46 ms 2424 KB Win!
14 Correct 46 ms 2444 KB Win!
15 Correct 45 ms 2448 KB Win!
16 Correct 54 ms 2452 KB Win!
17 Correct 57 ms 2492 KB Win!
18 Correct 38 ms 2492 KB Win!
19 Correct 44 ms 2492 KB Win!
20 Correct 66 ms 2492 KB Win!
21 Correct 46 ms 2600 KB Win!
22 Correct 46 ms 2600 KB Win!
23 Correct 46 ms 2600 KB Win!
24 Correct 49 ms 2600 KB Win!
25 Correct 46 ms 2600 KB Win!
26 Correct 47 ms 2600 KB Win!
27 Correct 44 ms 2628 KB Win!
28 Correct 45 ms 2628 KB Win!
29 Correct 51 ms 2628 KB Win!
30 Correct 50 ms 2628 KB Win!
31 Correct 45 ms 2628 KB Win!
32 Correct 45 ms 2628 KB Win!
33 Correct 51 ms 2628 KB Win!
34 Correct 51 ms 2628 KB Win!
35 Correct 40 ms 2656 KB Win!
36 Correct 44 ms 2656 KB Win!
37 Correct 40 ms 2744 KB Win!
38 Correct 43 ms 2744 KB Win!
39 Correct 42 ms 2744 KB Win!
40 Correct 64 ms 2744 KB Win!
41 Correct 45 ms 2744 KB Win!
42 Correct 53 ms 2744 KB Win!
43 Correct 43 ms 2744 KB Win!
44 Correct 43 ms 2772 KB Win!
45 Correct 51 ms 2772 KB Win!