| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 281969 |
2020-08-23T16:59:28 Z |
rqi |
Game (IOI13_game) |
C++14 |
|
7 ms |
384 KB |
#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
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
