oj.uz

Submission #200105

# Submission time Handle Problem Language Result Execution time Memory
200105 2020-02-05T11:09:44 Z johutha Game (IOI13_game) C++14
10 / 100
 13000 ms 256004 KB 
#include "game.h"
#include <vector>
#include <iostream>
#include <array>
#include <cassert>

#define int long long
#define par array<int,2>

using namespace std;

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct st2d
{
    vector<vector<int>> table;
    vector<int> ns;

    int query(par ql, par qr, int l, int r, par pos, int dim)
    {
        // cout << dim << " " << ql[dim] << " " << qr[dim] << " " << l << " " << r << " " << pos[0] << " " << pos[1] << "\n";
        if (ql[dim] <= l && r <= qr[dim])
        {
            if (dim == 1) return table[pos[0]][pos[1]];
            return query(ql, qr, 0, ns[1] - 1, pos, dim + 1);
        }
        if (r < ql[dim] || qr[dim] < l) return 0;
        par p1 = pos;
        par p2 = pos;
        p1[dim] = 2*pos[dim] + 1;
        p2[dim] = 2*pos[dim] + 2;
        return gcd(query(ql, qr, l, (l + r)/2, p1, dim), query(ql, qr, (l + r)/2 + 1, r, p2, dim));
    }

    void update(par k, int v, int l, int r, par pos, int dim)
    {
        if (l == r)
        {
            if (dim == 1) table[pos[0]][pos[1]] = v;
            else update(k, v, 0, ns[1] - 1, pos, dim + 1);
            return;
        }
        par p1 = pos;
        par p2 = pos;
        p1[dim] = 2*pos[dim] + 1;
        p2[dim] = 2*pos[dim] + 2;
        if (k[dim] <= (l + r)/2) update(k, v, l, (l + r)/2, p1, dim);
        else update(k, v, (l + r)/2 + 1, r, p2, dim);

        if (dim == 1) table[pos[0]][pos[1]] = gcd(table[pos[0]][2*pos[1] + 1], table[pos[0]][2*pos[1] + 2]); 
        else
        {
            for (int i = 0; i < 4*ns[1]; i++)
            {
                table[pos[0]][i] = gcd(table[2*pos[0] + 1][i], table[2*pos[0] + 2][i]);
            }
        }
    }

    void print()
    {
        for (auto t : table)
        {
            for (auto i : t) cout << i << " ";
            cout << "\n";
        }
        cout << "\n";
    }
};

st2d st;
int r;
int c;

void init(signed R, signed C)
{
    r = R;
    c = C;
    st.table.resize(4*R, vector<int>(4*C));
    st.ns.resize(2);
    st.ns[0] = R;
    st.ns[1] = C;
}

void update(signed P, signed Q, int K)
{
    // cout << "\n";
    st.update({P, Q}, K, 0, r - 1, {0, 0}, 0);
    // st.print();
}

int calculate(signed P, signed Q, signed U, signed V) 
{
    // cout << "\n";
    if (U < P) swap(U, P);
    if (V < Q) swap(Q, V);
    assert(P <= U);
    assert(Q <= V);
    int ret = st.query({P, Q}, {U, V}, 0, r - 1, {0, 0}, 0);
    // cout << "Ok: " << ret << "\n";
    return ret;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 1656 KB Output is correct
3 Correct 7 ms 1656 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 7 ms 1528 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 7 ms 1656 KB Output is correct
10 Correct 7 ms 1784 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Correct 5 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Execution timed out 13013 ms 130380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 1532 KB Output is correct
3 Correct 7 ms 1528 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 7 ms 1528 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 7 ms 1528 KB Output is correct
10 Correct 6 ms 1528 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Correct 2998 ms 133984 KB Output is correct
13 Correct 3290 ms 130552 KB Output is correct
14 Runtime error 186 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct
3 Correct 7 ms 1528 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 6 ms 1528 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 7 ms 1528 KB Output is correct
10 Correct 6 ms 1528 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Execution timed out 13084 ms 130032 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 1528 KB Output is correct
3 Correct 7 ms 1532 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 8 ms 1532 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 6 ms 1528 KB Output is correct
10 Correct 6 ms 1528 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Execution timed out 13104 ms 130236 KB Time limit exceeded
13 Halted 0 ms 0 KB -