Submission #668685

#	Time	Username	Problem	Language	Result	Execution time	Memory
668685		allin27x	Game (IOI14_game)	C++14	100 / 100	365 ms	16228 KiB

game

#include <iostream>
#include <vector>
using namespace std;
int gr_nr = 0;
vector<vector<int>> groups;
vector<int> vals;

void ds_gr(int a, int b){
    if (a==b) return;
    int m = (a+(b-a+1)/2);
    for (int i=a; i<m; i++){
        for (int j=m; j<=b; j++){
            groups[i][j] = gr_nr;
        }
    }
    vals[gr_nr] = (m-a)*(b-m+1);
    gr_nr++;
    ds_gr(a, m-1); ds_gr(m, b);
}
void initialize(int n){
    groups.resize(n, vector<int> (n,0));
    vals.resize(n, 0);
    ds_gr(0, n-1);
}

int hasEdge(int u, int v){
    return !(--vals[groups[min(u,v)][max(u,v)]]);
}

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