Submission #281969

#	Time	Username	Problem	Language	Result	Execution time	Memory
281969		rqi	Game (IOI13_game)	C++14	0 / 100	7 ms	384 KiB

game

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double ld;

#define f first
#define s second
#define mp make_pair
#define bk back()
#define pb push_back

const ld PI = acos((ld)-1);
const int MAXX = 1000000000;
const int MAXY = 1000000000;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
/**
 * Description: Hash map with the same API as unordered\_map, but \tilde 3x faster.
     * Initial capacity must be a power of 2 if provided.
 * Source: KACTL
 * Usage: ht<int,int> h({},{},{},{},{1<<16});
 */

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash { /// use most bits rather than just the lowest ones
    const uint64_t C = ll(2e18*PI)+71; // large odd number
    const int RANDOM = rng();
    ll operator()(ll x) const { /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
        return __builtin_bswap64((x^RANDOM)*C); }
};
template<class K,class V> using um = unordered_map<K,V,chash>;
template<class K,class V> using ht = gp_hash_table<K,V,chash>;
template<class K,class V> V get(ht<K,V>& u, K x) {
    auto it = u.find(x); return it == end(u) ? 0 : it->s; }

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

map<pair<pi, pi>, ll> seg;

bool check(pi a){
    if(a.f < 0 || a.f > MAXX) return 0;
    if(a.s < 0 || a.s > MAXY) return 0;
    return 1;
}

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    vpi x, y;
    x.pb(mp(P, P)); y.pb(mp(Q, Q));
    int curb = 0;
    while(true){
        pi newx = x.bk;
        if((((newx.f)>>curb)&1) == 1){
            newx.f-=(1<<curb);
        }
        if((((newx.s)>>curb)&1) == 0){
            newx.s+=(1<<curb);
        }
        if(check(newx)){
            x.pb(newx);
        }
        else break;
        curb++;
        // cout << newx.f << " " << newx.s << "\n";
        // cout << "HI\n";
        // cout.flush();
    }
    curb = 0;
    while(true){
        pi newy = y.bk;
        if((((newy.f)>>curb)&1) == 1){
            newy.f-=(1<<curb);
        }
        if((((newy.s)>>curb)&1) == 0){
            newy.s+=(1<<curb);
        }
        if(check(newy)){
            y.pb(newy);
        }
        else break;
        curb++;
        
    }
    for(auto a: x){
        for(auto b: y){
            seg[mp(a, b)] = gcd2(seg[mp(a, b)], K);
        }
    }
}

long long calculate(int P, int Q, int U, int V) {
    //cout << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
    vpi x, y;
    pi curx = mp(P, U);
    pi cury = mp(Q, V);
    int curb = 0;
    while(curx.f <= curx.s){
        if(((curx.f>>curb)&1) == 1){
            x.pb(mp(curx.f, curx.f+(1<<curb)-1));
            curx.f+=(1<<curb);
        }
        if(curx.f > curx.s) break;
        if(((curx.s>>curb)&1) == 0){
            x.pb(mp(curx.s-(1<<curb)+1, curx.s));
            curx.s-=(1<<curb);
        }
        curb++;
    }
    curb = 0;
    while(cury.f <= cury.s){
        if(((cury.f>>curb)&1) == 1){
            y.pb(mp(cury.f, cury.f+(1<<curb)-1));
            cury.f+=(1<<curb);
        }
        if(cury.f > cury.s) break;
        if(((cury.s>>curb)&1) == 0){
            y.pb(mp(cury.s-(1<<curb)+1, cury.s));
            cury.s-=(1<<curb);
        }
        curb++;
    }

    ll res = 0;
    // for(auto u: x){
    //     cout << u.f << " " << u.s << "\n";
    // }
    // cout << "\n";
    // for(auto u: y){
    //     cout << u.f << " " << u.s << "\n";
    // }
    for(auto a: x){
        for(auto b: y){
            if(seg.count(mp(a, b))) res = gcd2(res, seg[mp(a, b)]);
        }
    }
    /* ... */
    return res;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20