Submission #1043733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043733		pravcoder	Game (IOI14_game)	C++14	100 / 100	186 ms	9296 KiB

game

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

using namespace std;

typedef long long ll;
typedef short int si;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<si> vs;
typedef vector<vs> v2s;
typedef vector<v2s> v3s;

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

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

int minp3 = 0;

v2s trinum, upt, ept;
v3s cid;
v3i re;

void initialize(int n) {
    N = n;
    r = n*(n-1) / 2;
    int s = 1;
    while (s < n) {
        minp3++;
        s *= 3;
    }
    re.resize(minp3);
    cid.resize(minp3);
    trinum.resize(minp3);
    upt.resize(minp3);
    ept.resize(minp3);

    // setting up trinum, cid
    // cout << "Setting up trinum, cid... ";
    rep(c, n) {
        s = 1;
        rep(j, minp3) {
            s*=3;
            int tnum = floor(c/s);
            trinum[j].pb(tnum);
            cid[j].resize(tnum + 1);
            cid[j][tnum].pb(c);
        }
    }
    /*cout << "done\ncID:\n";
    for (auto tmp : cid) {
        for (auto tmp2 : tmp) {
            cout << tmp2.size() << " ";
        }
        cout << "\n";
    }*/
    // setting up ept, upt
    //cout << "Setting up ept, upt... ";
    s = 1;
    rep(j, minp3) {
        s *= 3;
        upt[j].resize(cid[j].size(), 0);
        int ptr = 0;
        while (ptr < n) {
            ept[j].pb(floor((min(s, n - ptr)*3 - 1)/s) + 1);
            ptr += s;
        }
    }
    /*cout << "done\nept:\n";
    for (auto tmp : ept) {
        for (auto tmp2 : tmp) {
            cout << tmp2 << " ";
        }
        cout << "\n";
    }*/
    //setting up re
    //cout << "Setting up re\n";
    rep(j, minp3) {
        re[j].resize(cid[j].size());
        rep(k, cid[j].size()) {
            if (j == 0) {
                if (ept[j][k] == 3) re[j][k].resize(3, 1);
                else if (ept[j][k] == 2) 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());
                }
            }
            //cout << "Finished setting up re[" << j << "][" << k << "]\n";
        }
        //cout << "Finished setting up re[" << j << "]\n";
    }
    /*cout << "re:\n";
    for (auto tmp : re) {
        for (auto tmp2 : tmp) {
            cout << "{";
            for (auto tmp3 : tmp2) {
                cout << tmp3 << ",";
            }
            cout << "} ";
        }
        cout << "\n";
    }*/
}


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++;
    //cout << "tri level of both cities is " << l;
    int t = trinum[l][u];
    //cout << "\ntri id is " << t << "\n";
    if (l == 0) {
        return ++upt[l][t] > 1 || ept[l][t] < 3;
    } else {
        int tu = trinum[l-1][u];
        int tv = trinum[l-1][v];
        //cout << tu << " " << tv << "\n";
        int renum = (3 + (1 - (tu + tv - 6*t))) % 3;
        //cout << "renum is " << renum << "\n";
        //cout << "remaining edges between tris: " << re[l][t][renum] << "\n";
        if (ept[l][t] < 2 || --re[l][t][renum] == 0) {
            return ++upt[l][t] > 1 || ept[l][t] < 3;
        } else return 0;
    }
}

Compilation message (stderr)

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

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