제출 #200885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
200885		johutha	게임 (IOI13_game)	C++17	37 / 100	13091 ms	9720 KiB

game

#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include "game.h"

#define int long long
#define seed 4142

using namespace std;

mt19937 rng(seed);
uniform_int_distribution<int> uni(0, 1e12);

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

struct node;

using node_ptr = unique_ptr<node>;

struct node
{
    node_ptr l, r;
    int pos, lp, rp;
    int val;
    int cv;
    int x;

    void recompute()
    {
        cv = val;
        lp = pos;
        rp = pos;
        if (l)
        {
            lp = l->lp;
            cv = gcd(cv, l->cv);
        }
        if (r)
        {
            rp = r->rp;
            cv = gcd(cv, r->cv);
        }
    }

    node(int ipos, int ival) : pos(ipos), val(ival), x(uni(rng)) { recompute(); }

    static node_ptr merge(node_ptr l, node_ptr r)
    {
        if (!l) return r;
        if (!r) return l;

        if (l->x > r->x)
        {
            l->r = merge(move(l->r), move(r));
            l->recompute();
            return l;
        }
        else
        {
            r->l = merge(move(l), move(r->l));
            r->recompute();
            return r;
        }
    }

    static pair<node_ptr,node_ptr> split(node_ptr rt, int pos)
    {
        if (!rt) return {};

        if (pos <= rt->pos)
        {
            node_ptr l;
            tie(l, rt->l) = split(move(rt->l), pos);
            if (l) l->recompute();
            if (rt) rt->recompute();
            return {move(l), move(rt)};
        }
        else
        {
            node_ptr r;
            tie(rt->r, r) = split(move(rt->r), pos);
            if (r) r->recompute();
            if (rt) rt->recompute();
            return {move(rt), move(r)};
        }
    }

    void print(int ind)
    {
        if (l) l->print(ind + 1);
        for (int i = 0; i < ind; i++) cout << "  ";
        cout << pos << " " << val << " " << cv << "  " << lp << " " << rp << "\n";
        if (r) r->print(ind + 1);
    }

    static node_ptr insert(node_ptr rt, int pos, int v)
    {
        node_ptr nw = make_unique<node>(pos, v);
        auto p = split(move(rt), pos);
        p.first = merge(move(p.first), move(nw));
        p.second = merge(move(p.first), move(p.second));
        return move(p.second);
    }

    bool contains(int key)
    {
        if (pos == key) return true;
        if (pos < key && r) return r->contains(key);
        if (key < pos && l) return l->contains(key);
        return false;
    }

    void update(int k, int nv)
    {
        if (k == pos) val = nv;
        if (k < pos) l->update(k, nv);
        if (k > pos) r->update(k, nv);
        recompute();
    }

    int query(int ql, int qr)
    {
        if (rp < ql || qr < lp) return 0;
        if (ql <= lp && rp <= qr) { return cv; }
        int res = 0;
        if (ql <= pos && pos <= qr) res = gcd(val, res);
        if (l) res = gcd(res, l->query(ql, qr));
        if (r) res = gcd(res, r->query(ql, qr));
        return res;
    }
};

int r;
vector<node_ptr> alln;

void init(signed R, signed C)
{
    r = R;
    alln.resize(R);
}

void update(signed P, signed Q, int K)
{
    if (alln[P] && alln[P]->contains(Q))
    {
        alln[P]->update(Q, K);
    }
    else
    {
        alln[P] = node::insert(move(alln[P]), Q, K);
    }
/*
    cout << "\nUpdate:\n";
    for (int i = 0; i < r; i++)
    {
        if (alln[i])
        {
            cout << i << ":\n";
            alln[i]->print(i);
        }
    } 
*/
}

int calculate(signed P, signed Q, signed U, signed V)
{
    if (P > U) swap(P, U);
    if (Q > V) swap(Q, V);

    int res = 0;
    // cout << "\nQuery:\n";
    for (int i = P; i <= U; i++)
    {
        if (!alln[i]) continue;
        int mr = alln[i]->query(Q, V);
        // cout << i << " " << mr << "\n";
        res = gcd(res, mr);
    }
    return res;
}

컴파일 시 표준 에러 (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: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20