Ideone.com

fork download

copy

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
 
#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
 
#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(X) ((int) ((X).size()))
using namespace std;
 
const ll MOD = 1e9 + 7;
 
int sz;
struct Matrix {
    ll x[22][22];
 
    void print() {
        REP(i,sz) {
            REP(j,sz) cout << x[i][j] << ' '; cout << endl;
        }
        cout << endl;
    }
} A, I;
 
struct Vector {
    ll x[22];
 
    void print() {
        PR0(x, sz);
    }
} f;
 
Vector update(const Vector& f, const Matrix& A) {
    Vector res;
    REP(i,sz) {
        res.x[i] = 0;
        REP(j,sz)
            res.x[i] = (res.x[i] + A.x[i][j] * f.x[j]) % MOD;
    }
    return res;
}
 
Matrix operator * (const Matrix& a, const Matrix& b) {
    Matrix res;
    REP(i,sz) REP(j,sz) {
        res.x[i][j] = 0;
        REP(k,sz)
            res.x[i][j] = (res.x[i][j] + a.x[i][k] * b.x[k][j]) % MOD;
    }
    return res;
}
 
Matrix power(const Matrix& a, int k) {
    if (k == 0) return I;
    if (k == 1) return a;
 
    Matrix mid = power(a, k >> 1);
    mid = mid * mid;
 
    if (k & 1) return mid * a;
    return mid;
}
 
const int MN = 22;
int m, n, q, id[MN][MN];
 
const int di[5] = {-1,1,0,0,0};
const int dj[5] = {0,0,-1,1,0};
 
bool outside(int u, int v) {
    return u < 1 || v < 1 || u > m || v > n;
}
 
void init() {
    int cur = 0;
    FOR(i,1,m) FOR(j,1,n) id[i][j] = cur++;
 
    memset(I.x, 0, sizeof I.x);
    memset(A.x, 0, sizeof A.x);
 
    sz = m * n;
    REP(i,sz) I.x[i][i] = 1;
 
    FOR(i,1,m) FOR(j,1,n) {
        REP(dir,5) {
            int ii = i + di[dir], jj = j + dj[dir];
            if (outside(ii, jj)) continue;
 
            A.x[ id[i][j] ][ id[ii][jj] ] = 1;
        }
    }
}
 
int main() {
    ios :: sync_with_stdio(false);
     {
		n = 5; m = 4; q = 10000;
        init();
 
        memset(f.x, 0, sizeof f.x);
        f.x[0] = 1;
 
        int cur_time = 1;
 
        for(int i = 0; i < q; i++) {
            int typ = 1;
            int x = 1, y = 1, t = i * 1000 + 10;
 
            // update until time moment t-1
            Matrix up = power(A, t - 1 - cur_time);
            f = update(f, up);
 
            if (typ == 2) {
                // cannot go to cell (x, y)
                REP(dir,5) {
                    int xx = x + di[dir], yy = y + dj[dir];
                    if (outside(xx, yy)) continue;
 
                    A.x[ id[x][y] ][ id[xx][yy] ] = 0;
                }
            }
            f = update(f, A);
 
            if (typ == 1) {
                cout << (int) f.x[id[x][y]] << '\n';
            }
            cur_time = t;
 
            if (typ == 3) {
                // can now go to cell (x, y)
                REP(dir,5) {
                    int xx = x + di[dir], yy = y + dj[dir];
                    if (outside(xx, yy)) continue;
 
                    A.x[ id[x][y] ][ id[xx][yy] ] = 1;
                }
            }
        }
    }
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk8PV9iOyBpKyspCiNkZWZpbmUgRk9SRChpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk+PV9iOyBpLS0pCiNkZWZpbmUgUkVQKGksYSkgZm9yKGludCBpPTAsX2E9KGEpOyBpPF9hOyBpKyspCiNkZWZpbmUgRUFDSChpdCxhKSBmb3IoX190eXBlb2YoYS5iZWdpbigpKSBpdCA9IGEuYmVnaW4oKTsgaXQgIT0gYS5lbmQoKTsgKytpdCkKCiNkZWZpbmUgREVCVUcoeCkgeyBjb3V0IDw8ICN4IDw8ICIgPSAiOyBjb3V0IDw8ICh4KSA8PCBlbmRsOyB9CiNkZWZpbmUgUFIoYSxuKSB7IGNvdXQgPDwgI2EgPDwgIiA9ICI7IEZPUihfLDEsbikgY291dCA8PCBhW19dIDw8ICcgJzsgY291dCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIwKGEsbikgeyBjb3V0IDw8ICNhIDw8ICIgPSAiOyBSRVAoXyxuKSBjb3V0IDw8IGFbX10gPDwgJyAnOyBjb3V0IDw8IGVuZGw7IH0KCiNkZWZpbmUgc3FyKHgpICgoeCkgKiAoeCkpCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgU1ooWCkgKChpbnQpICgoWCkuc2l6ZSgpKSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGxsIE1PRCA9IDFlOSArIDc7CgppbnQgc3o7CnN0cnVjdCBNYXRyaXggewogICAgbGwgeFsyMl1bMjJdOwoKICAgIHZvaWQgcHJpbnQoKSB7CiAgICAgICAgUkVQKGksc3opIHsKICAgICAgICAgICAgUkVQKGosc3opIGNvdXQgPDwgeFtpXVtqXSA8PCAnICc7IGNvdXQgPDwgZW5kbDsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9IEEsIEk7CgpzdHJ1Y3QgVmVjdG9yIHsKICAgIGxsIHhbMjJdOwoKICAgIHZvaWQgcHJpbnQoKSB7CiAgICAgICAgUFIwKHgsIHN6KTsKICAgIH0KfSBmOwoKVmVjdG9yIHVwZGF0ZShjb25zdCBWZWN0b3ImIGYsIGNvbnN0IE1hdHJpeCYgQSkgewogICAgVmVjdG9yIHJlczsKICAgIFJFUChpLHN6KSB7CiAgICAgICAgcmVzLnhbaV0gPSAwOwogICAgICAgIFJFUChqLHN6KQogICAgICAgICAgICByZXMueFtpXSA9IChyZXMueFtpXSArIEEueFtpXVtqXSAqIGYueFtqXSkgJSBNT0Q7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpNYXRyaXggb3BlcmF0b3IgKiAoY29uc3QgTWF0cml4JiBhLCBjb25zdCBNYXRyaXgmIGIpIHsKICAgIE1hdHJpeCByZXM7CiAgICBSRVAoaSxzeikgUkVQKGosc3opIHsKICAgICAgICByZXMueFtpXVtqXSA9IDA7CiAgICAgICAgUkVQKGssc3opCiAgICAgICAgICAgIHJlcy54W2ldW2pdID0gKHJlcy54W2ldW2pdICsgYS54W2ldW2tdICogYi54W2tdW2pdKSAlIE1PRDsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCk1hdHJpeCBwb3dlcihjb25zdCBNYXRyaXgmIGEsIGludCBrKSB7CiAgICBpZiAoayA9PSAwKSByZXR1cm4gSTsKICAgIGlmIChrID09IDEpIHJldHVybiBhOwoKICAgIE1hdHJpeCBtaWQgPSBwb3dlcihhLCBrID4+IDEpOwogICAgbWlkID0gbWlkICogbWlkOwoKICAgIGlmIChrICYgMSkgcmV0dXJuIG1pZCAqIGE7CiAgICByZXR1cm4gbWlkOwp9Cgpjb25zdCBpbnQgTU4gPSAyMjsKaW50IG0sIG4sIHEsIGlkW01OXVtNTl07Cgpjb25zdCBpbnQgZGlbNV0gPSB7LTEsMSwwLDAsMH07CmNvbnN0IGludCBkals1XSA9IHswLDAsLTEsMSwwfTsKCmJvb2wgb3V0c2lkZShpbnQgdSwgaW50IHYpIHsKICAgIHJldHVybiB1IDwgMSB8fCB2IDwgMSB8fCB1ID4gbSB8fCB2ID4gbjsKfQoKdm9pZCBpbml0KCkgewogICAgaW50IGN1ciA9IDA7CiAgICBGT1IoaSwxLG0pIEZPUihqLDEsbikgaWRbaV1bal0gPSBjdXIrKzsKCiAgICBtZW1zZXQoSS54LCAwLCBzaXplb2YgSS54KTsKICAgIG1lbXNldChBLngsIDAsIHNpemVvZiBBLngpOwoKICAgIHN6ID0gbSAqIG47CiAgICBSRVAoaSxzeikgSS54W2ldW2ldID0gMTsKCiAgICBGT1IoaSwxLG0pIEZPUihqLDEsbikgewogICAgICAgIFJFUChkaXIsNSkgewogICAgICAgICAgICBpbnQgaWkgPSBpICsgZGlbZGlyXSwgamogPSBqICsgZGpbZGlyXTsKICAgICAgICAgICAgaWYgKG91dHNpZGUoaWksIGpqKSkgY29udGludWU7CgogICAgICAgICAgICBBLnhbIGlkW2ldW2pdIF1bIGlkW2lpXVtqal0gXSA9IDE7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGlvcyA6OiBzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgIHsKCQluID0gNTsgbSA9IDQ7IHEgPSAxMDAwMDsKICAgICAgICBpbml0KCk7CgogICAgICAgIG1lbXNldChmLngsIDAsIHNpemVvZiBmLngpOwogICAgICAgIGYueFswXSA9IDE7CgogICAgICAgIGludCBjdXJfdGltZSA9IDE7CgogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspIHsKICAgICAgICAgICAgaW50IHR5cCA9IDE7CiAgICAgICAgICAgIGludCB4ID0gMSwgeSA9IDEsIHQgPSBpICogMTAwMCArIDEwOwoKICAgICAgICAgICAgLy8gdXBkYXRlIHVudGlsIHRpbWUgbW9tZW50IHQtMQogICAgICAgICAgICBNYXRyaXggdXAgPSBwb3dlcihBLCB0IC0gMSAtIGN1cl90aW1lKTsKICAgICAgICAgICAgZiA9IHVwZGF0ZShmLCB1cCk7CgogICAgICAgICAgICBpZiAodHlwID09IDIpIHsKICAgICAgICAgICAgICAgIC8vIGNhbm5vdCBnbyB0byBjZWxsICh4LCB5KQogICAgICAgICAgICAgICAgUkVQKGRpciw1KSB7CiAgICAgICAgICAgICAgICAgICAgaW50IHh4ID0geCArIGRpW2Rpcl0sIHl5ID0geSArIGRqW2Rpcl07CiAgICAgICAgICAgICAgICAgICAgaWYgKG91dHNpZGUoeHgsIHl5KSkgY29udGludWU7CgogICAgICAgICAgICAgICAgICAgIEEueFsgaWRbeF1beV0gXVsgaWRbeHhdW3l5XSBdID0gMDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmID0gdXBkYXRlKGYsIEEpOwoKICAgICAgICAgICAgaWYgKHR5cCA9PSAxKSB7CiAgICAgICAgICAgICAgICBjb3V0IDw8IChpbnQpIGYueFtpZFt4XVt5XV0gPDwgJ1xuJzsKICAgICAgICAgICAgfQogICAgICAgICAgICBjdXJfdGltZSA9IHQ7CgogICAgICAgICAgICBpZiAodHlwID09IDMpIHsKICAgICAgICAgICAgICAgIC8vIGNhbiBub3cgZ28gdG8gY2VsbCAoeCwgeSkKICAgICAgICAgICAgICAgIFJFUChkaXIsNSkgewogICAgICAgICAgICAgICAgICAgIGludCB4eCA9IHggKyBkaVtkaXJdLCB5eSA9IHkgKyBkaltkaXJdOwogICAgICAgICAgICAgICAgICAgIGlmIChvdXRzaWRlKHh4LCB5eSkpIGNvbnRpbnVlOwoKICAgICAgICAgICAgICAgICAgICBBLnhbIGlkW3hdW3ldIF1bIGlkW3h4XVt5eV0gXSA9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0=

Time limit exceeded #stdin #stdout 5s 3464KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/6zbkSM

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language