Submission #295223

#	Time	Username	Problem	Language	Result	Execution time	Memory
295223		arayi	Game (IOI14_game)	C++17	100 / 100	667 ms	28292 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;


int col[2020][2020];
int n, t[10000];
void bld(int l = 0, int r = n - 1, int nd = 1)
{
    if(l == r) return;
    int mid = (l + r) / 2;
    t[nd] = (r - mid) * (mid - l + 1);
    bld(l, mid, nd * 2);
    bld(mid + 1, r, nd * 2 + 1);
}
int qry(int u, int v, int l = 0, int r = n - 1, int nd = 1)
{
    int mid = (l + r) / 2;
    if(u <= mid && v > mid)
        return --t[nd];
    else if(u <= mid && v <= mid) return qry(u, v, l, mid, nd * 2);
    else return qry(u, v, mid + 1, r, nd * 2 + 1);
}
void initialize(int N)
{
    n = N;
    bld();
}

int hasEdge(int u, int v) {
    if(col[u][v]) return col[u][v] - 1;
    if(u == v) return 0;
    int sm = qry(min(u, v), max(u, v));
    //cout << u << " " << v << " " << sm << endl;
    if(sm) sm = 0;
    else sm = 1;
    col[u][v] = col[v][u] = sm + 1;
    return sm;
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58