Submission #1043668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043668		pravcoder	Game (IOI14_game)	C++17	0 / 100	1 ms	348 KiB

game

#include "game.h"
#include <vector>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<ll> vl;
typedef vector<vl> v2l;
typedef vector<v2l> v3l;

#define pb push_back
#define rep(i, n) for (int i=0; i<n; i++)

int i = 0;
int r = 0;
int N = 0;

v2i trinum, upt, ept;
v3i cid;
v3l re;

void initialize(int n) {
    N = n;
    r = n*(n-1) / 2;
    re.resize(7);
    cid.resize(7);
    trinum.resize(7);
    upt.resize(7);
    ept.resize(7);
    int s;
    // setting up trinum, cid
    rep(c, n) {
        s = 1;
        rep(j, 7) {
            s*=3;
            int tnum = floor(c/s);
            trinum[j].pb(tnum);
            cid[j].resize(tnum + 1);
            cid[j][tnum].pb(c);
        }
    }
    // setting up ept, upt
    s = 1;
    rep(j, 7) {
        s *= 3;
        upt[j].resize(cid[j].size(), 0);
        int ptr = 0;
        while (ptr < n) {
            ept[j].pb(min(s, n - ptr));
            ptr += s;
        }
    }
    //setting up re
    rep(j, 7) {
        rep(k, cid[j].size()) {
            if (j == 0) {
                if (ept[j][k] == 3) re[j][k].resize(3, 1);
                else re[j][k].resize(ept[j][k]-1, 1);
            } else {
                if (ept[j][k] == 3) {
                    re[j][k].pb(cid[j-1][3*k].size()*cid[j-1][3*k + 1].size());
                    re[j][k].pb(cid[j-1][3*k + 1].size()*cid[j-1][3*k + 2].size());
                    re[j][k].pb(cid[j-1][3*k + 2].size()*cid[j-1][3*k].size());
                } else if (ept[j][k] == 2) {
                    re[j][k].pb(cid[j-1][3*k].size()*cid[j-1][3*k + 1].size());
                }
            }
        }
    }

}


int hasEdge(int u, int v) {
    i++;
    if (v<u) swap(u,v);
    int l = 0; // lvl of the original triangle
    while (trinum[l][u] != trinum[l][v]) l++;
    int t = trinum[l][u];
    if (l == 0) {
        return ++upt[l][t] > 1;
    } else {
        int tu = trinum[l-1][u];
        int tv = trinum[l-1][v];
        int renum = (1 - (tu + tv - 6*t)) % 3;
        if (--re[l][t][renum] == 0) {
            return ++upt[l][t] > 1;
        } else return 0;
    }
}

Compilation message (stderr)

game.cpp: In function 'void initialize(int)':
game.cpp:19:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define rep(i, n) for (int i=0; i<n; i++)
......
   62 |         rep(k, cid[j].size()) {
      |             ~~~~~~~~~~~~~~~~      
game.cpp:62:9: note: in expansion of macro 'rep'
   62 |         rep(k, cid[j].size()) {
      |         ^~~

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