제출 #200105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200105		johutha	게임 (IOI13_game)	C++14	10 / 100	13104 ms	256004 KiB

game

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20