QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#219648 | #5309. Guess Cycle Length | woshiluo | AC ✓ | 1ms | 3564kb | C++20 | 2.5kb | 2023-10-19 17:05:42 | 2023-10-19 17:05:43 |
Judging History
answer
/*
* tmp.cpp 2023-10-19
* Copyright (C) 2023 Woshiluo Luo <[email protected]>
*
* 「Two roads diverged in a wood,and I—
* I took the one less traveled by,
* And that has made all the difference.」
*
* Distributed under terms of the GNU GNU AGPLv3+ license.
*/
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <map>
#include <random>
#include <vector>
#include <algorithm>
typedef const int cint;
typedef uint32_t uint;
typedef long long ll;
typedef unsigned long long ull;
inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <class T>
T aabs( T a ) { return a < 0? -a: a; }
template <typename T>
T read() {
T sum = 0, fl = 1;
char ch = getchar();
for (; isdigit(ch) == 0; ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <class T>
T pow( T a, int p ) {
T res = 1;
while( p ) {
if( p & 1 )
res = res * a;
a = a * a;
p >>= 1;
}
return res;
}/*}}}*/
std::random_device seed;
std::mt19937_64 rnd(seed());
// int walk( unsigned int x ) {
// printf( "walk %d\n", x );
// fflush(stdout);
// cint res = read<int>();
// return res;
// }
//
int gen( cint l, cint r ) {
return ( rnd() % ( r - l ) ) + l;
}
int n = 19260817;
ll cur = 0;
int walk( unsigned int x ) {
cur += x;
cur %= n;
return cur;
}
void guess( cint p ) {
printf( "guess %d\n", p );
fflush(stdout);
std::exit(0);
}
ll gcd( ll a, ll b ) { return b? gcd( b, a % b ): a; }
int main() {
#ifdef woshiluo
freopen( "tmp2.in", "r", stdin );
freopen( "tmp2.out", "w", stdout );
#endif
cur = 0;
std::map<int, ll> mp;
unsigned long long sum = 0;
int k = 3333;
int min = 0;
for( int i = 0; i < k; i ++ ) {
chk_Max( min, walk( gen( 1, 1e9 ) ) );
}
for( int i = 0; i < k; i ++ ) {
int current = walk(1);
sum += 1;
if( mp.count(current) ) {
guess( sum - mp[current] );
}
mp[current] = sum;
}
int current = walk(min); sum += min;
for( int i = 0; i < k; i ++ ) {
if( mp.count(current) ) {
guess( sum - mp[current] );
}
mp[current] = sum;
current = walk(k);
sum += k;
}
return -1;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3292kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #2:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #3:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3300kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3344kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #7:
score: 0
Accepted
time: 1ms
memory: 3280kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #8:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #9:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #10:
score: 0
Accepted
time: 1ms
memory: 3296kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #11:
score: 0
Accepted
time: 1ms
memory: 3280kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #12:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #13:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #14:
score: 0
Accepted
time: 1ms
memory: 3292kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #15:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #16:
score: 0
Accepted
time: 1ms
memory: 3276kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #17:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #18:
score: 0
Accepted
time: 1ms
memory: 3340kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #19:
score: 0
Accepted
time: 1ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #20:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #21:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #22:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #23:
score: 0
Accepted
time: 0ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #24:
score: 0
Accepted
time: 1ms
memory: 3356kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #25:
score: 0
Accepted
time: 1ms
memory: 3296kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #26:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #27:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #29:
score: 0
Accepted
time: 1ms
memory: 3220kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #30:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #31:
score: 0
Accepted
time: 0ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #32:
score: 0
Accepted
time: 1ms
memory: 3244kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #33:
score: 0
Accepted
time: 1ms
memory: 3260kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #34:
score: 0
Accepted
time: 1ms
memory: 3228kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #35:
score: 0
Accepted
time: 1ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #36:
score: 0
Accepted
time: 1ms
memory: 3280kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #37:
score: 0
Accepted
time: 1ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #38:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #39:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #40:
score: 0
Accepted
time: 1ms
memory: 3296kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #41:
score: 0
Accepted
time: 1ms
memory: 3284kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #42:
score: 0
Accepted
time: 1ms
memory: 3352kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #43:
score: 0
Accepted
time: 1ms
memory: 3304kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #44:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #45:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #46:
score: 0
Accepted
time: 0ms
memory: 3292kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #47:
score: 0
Accepted
time: 1ms
memory: 3344kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #48:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #49:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #50:
score: 0
Accepted
time: 1ms
memory: 3352kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #51:
score: 0
Accepted
time: 1ms
memory: 3288kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #52:
score: 0
Accepted
time: 1ms
memory: 3352kb
input:
output:
guess 19260817
result:
ok OK, guesses=0
Test #53:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
output:
guess 19260817
result:
ok OK, guesses=0