답안 #70376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70376	2018-08-22T17:43:24 Z	Benq	Mini tetris (IOI16_tetris)	C++14	100 / 100	73 ms	2772 KB

tetris

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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!

답안 #70376

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 10.0 / 10.0

Subtask #4 21.0 / 21.0

Subtask #5 54.0 / 54.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
10.0 / 10.0

Subtask #4
21.0 / 21.0

Subtask #5
54.0 / 54.0