QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#444941 | #8782. Schoolgirls | ucup-team1338 | WA | 3ms | 3832kb | C++20 | 3.0kb | 2024-06-15 22:33:01 | 2024-06-15 22:33:02 |
Judging History
answer
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int; using i64 = long long; using ui64 = unsigned long long; using i128 = __int128;
const int INF = 1e9; const i64 LLNF = 4e18;
template< class Tp > void chkmax( Tp &x, Tp y ) { x = max( x, y ); }
template< class Tp > void chkmin( Tp &x, Tp y ) { x = min( x, y ); }
int log( int x ) { return 31 - __builtin_clz( x ); }
int log( i64 x ) { return 63 - __builtin_clzll( x ); }
mt19937_64 rng( 19260817 );
i64 rand( i64 L, i64 R ) { return rng( ) % ( R - L + 1 ) + L; }
i64 qpow( i64 a, i64 b, i64 p ) { i64 c = 1; for( ; b; b >>= 1, a = ( i128 ) a * a % p ) if( b & 1 ) c = ( i128 ) c * a % p; return c; }
vector< int > getp( int n ) { vector< int > pn; for( int p = 2; p * p <= n; p ++ ) if( n % p == 0 ) { pn.emplace_back( p ); while( n % p == 0 ) n /= p; } if( n > 1 ) pn.emplace_back( n ); return pn; }
// miller-rabin
bool isp( i64 n ) {
int a = 0; i64 k = n - 1; while( k % 2 == 0 ) a ++, k /= 2;
constexpr int tests = 100;
for( int _ = 1; _ <= tests; _ ++ ) {
i64 x = rand( 1, n - 1 );
if( gcd( n, x ) > 1 ) return false;
i64 y = qpow( x, k, n );
for( int i = 0; i <= a - 1; i ++ ) {
if( ( y != 1 && y != n - 1 ) && ( i128 ) y * y % n == 1 ) return false;
y = ( i128 ) y * y % n;
}
if( y != 1 ) return false;
}
return true;
}
// return p, where p is any prime mod n = 1.
i64 findp( int n ) {
i64 M = 1e15; i64 K = M / n;
while( true ) { i64 p = rand( 1, K ) * n + 1; if( isp( p ) ) return p; }
}
// return g ** ( ( p - 1 ) / n ) mod p, where g is any primitive root.
i64 findg( i64 p, int n ) {
assert( ( p - 1 ) % n == 0 );
vector< int > pn = getp( n );
while( true ) {
i64 g = rand( 1, p - 1 ); i64 h = qpow( g, ( p - 1 ) / n, p );
bool good = true; for( int q : pn ) if( qpow( h, n / q, p ) == 1 ) good = false;
if( good ) return h;
}
}
void solve( ) {
int n, m, k; cin >> n >> m >> k; int N = lcm( 2, n ); i64 p = findp( N );
vector< i64 > z( n + m ); i64 e = findg( p, n );
for( int i = 0; i < n; i ++ ) z[i] = qpow( e, i, p );
for( int i = n; i < n + m; i ++ ) { int a, b, c; cin >> a >> b >> c; a --, b --, c --; z[i] = ( z[a] + z[c] - z[b] + p ) % p; }
while( k -- ) {
int r; cin >> r; vector< i64 > I( r ); for( int j = 0; j < r; j ++ ) cin >> I[j], I[j] --;
i64 z0 = 0; for( int i : I ) z0 = ( z0 + z[i] ) % p;
vector< i64 > y; for( int i : I ) y.emplace_back( ( ( i128 ) r * z[i] % p - z0 + p ) % p ); sort( y.begin( ), y.end( ) );
if( N % r != 0 ) {
if( y[0] == y[r - 1] ) cout << "Yes" << "\n";
else cout << "No" << "\n";
}
else {
i64 f = qpow(e,N/r,p);
bool good = true; for( i64 x : y ) { i64 fx = ( i128 ) x * f % p; good &= binary_search( y.begin( ), y.end( ), fx ); }
if( good ) cout << "Yes" << "\n";
else cout << "No" << "\n";
}
}
}
int main( ) {
ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
int T = 1; while( T -- ) solve( ); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
3 6 8 1 2 3 3 1 4 5 4 3 3 1 2 4 5 3 4 5 2 6 4 7 6 5 1 2 3 1 3 2 3 1 1 8 4 2 5 6 7 3 2 1 4 3 6 5 9 3 4 7 9 4 1 3 2 8
output:
Yes Yes Yes No No No Yes No
result:
ok 8 token(s): yes count is 4, no count is 4
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
12 0 1 12 12 11 10 9 8 7 6 5 4 3 2 1
output:
Yes
result:
ok YES
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 3832kb
input:
3 0 6685 5 1 3 1 2 2 3 1 2 3 5 3 1 3 3 1 4 1 1 1 3 3 3 2 1 5 2 3 2 1 3 6 2 2 3 2 3 1 5 3 1 2 3 2 3 3 3 2 5 3 2 2 2 3 5 2 2 3 3 1 6 3 3 1 3 1 3 6 2 3 3 2 2 1 5 2 2 3 2 2 6 2 3 3 2 1 3 6 2 2 2 2 1 3 3 3 1 2 4 3 2 1 1 5 3 1 3 2 3 4 3 1 1 2 4 2 2 2 3 3 1 2 2 4 2 3 3 1 3 2 2 2 4 1 2 2 3 3 3 3 3 4 1 3 1 3...
output:
No Yes No No Yes No No No No No No No No No No No Yes No No No No No No Yes No Yes No No No No No No No No No No No No Yes No No No No No No No No Yes No No No No No Yes No Yes No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No Yes No No No No No N...
result:
wrong answer expected NO, found YES [108th token]