Submission #70376

#	Time	Username	Problem	Language	Result	Execution time	Memory
70376		Benq	Mini tetris (IOI16_tetris)	C++14	100 / 100	73 ms	2772 KiB

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 10 / 10
• Subtask 4: 21 / 21
• Subtask 5: 54 / 54