QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107564 | #884. Joining Treasure Hunt | Sorting | WA | 661ms | 59504kb | C++20 | 3.3kb | 2023-05-22 00:43:31 | 2023-05-22 00:43:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const ll mod = (119 << 23) + 1, root = 62; // = 998244353
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.
typedef vector<ll> vl;
ll modpow(ll b, ll e) {
ll ans = 1;
for (; e; b = b * b % mod, e /= 2)
if (e & 1) ans = ans * b % mod;
return ans;
}
void ntt(vl &a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z - mod : z);
}
}
vl conv(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
int inv = modpow(n, mod - 2);
vl L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
int n , m ;
vl a , b ;
vl hh1 , hh2 , hh3 , hh4 ;
ll enc[ 50 ] ;
void solve ( ) {
cin >> n >> m ;
a.resize ( n ) , b.resize ( m ) ;
auto ord = [ & ] ( char c ) {
if ( c == 'n' ) { return 0 ; }
if ( c == 'w' ) { return 1 ; }
if ( c == 's' ) { return 2 ; }
if ( c == 'e' ) { return 3 ; }
};
for ( int i = 0 ; i < 50 ; ++ i ) {
enc[ i ] = rng ( ) ;
}
for ( int i = 0 ; i < n ; ++ i ) {
char c ; int x ;
cin >> c ;
if ( c == '?' ) { a[ i ] = 0 ; continue ; }
cin >> x ;
a[ i ] = enc[ ord ( c ) * 8 + x ] % mod ;
}
for ( int i = 0 ; i < m ; ++ i ) {
char c ; int x ;
cin >> c ;
if ( c == '?' ) { b[ i ] = 0 ; continue ; }
cin >> x ;
b[ i ] = enc[ ord ( c ) * 8 + x ] % mod ;
}
reverse ( b.begin ( ) , b.end ( ) ) ;
hh1.resize ( n ) , hh2.resize ( m ) ;
for ( int i = 0 ; i < n ; ++ i ) {
hh1[ i ] = ( a[ i ] * a[ i ] ) % mod ;
}
for ( int i = 0 ; i < m ; ++ i ) {
hh2[ i ] = b[ i ] ;
}
auto ret1 = conv ( hh1 , hh2 ) ;
hh3.resize ( n ) , hh4.resize ( m ) ;
for ( int i = 0 ; i < n ; ++ i ) {
hh3[ i ] = a[ i ] ;
}
for ( int i = 0 ; i < m ; ++ i ) {
hh4[ i ] = ( b[ i ] * b[ i ] ) % mod ;
}
auto ret2 = conv ( hh3 , hh4 ) ;
int ans = 0 ;
for ( int i = 0 ; i + m - 1 < n ; ++ i ) {
if ( ret1[ i + ( m - 1 ) ] == ret2[ i + ( m - 1 ) ] ) { ++ ans ; }
}
cout << ans << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3432kb
input:
4 3 n 4 e 1 ? s 5 ? e 1 ?
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
4 3 n 4 e 1 w 3 s 5 ? e 1 ?
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 661ms
memory: 59504kb
input:
400000 200000 ? ? e 7 e 7 ? ? ? e 7 e 7 ? ? e 7 ? e 7 e 7 ? e 7 ? ? ? e 7 ? ? e 7 ? ? ? ? e 7 ? e 7 ? ? e 7 ? ? e 7 e 7 e 7 ? ? ? ? ? ? e 7 ? e 7 ? ? ? ? ? ? ? ? ? ? e 7 e 7 ? ? e 7 ? e 7 e 7 ? ? e 7 e 7 e 7 ? e 7 e 7 ? ? ? ? ? ? e 7 e 7 ? ? e 7 ? ? ? ? e 7 ? ? ? e 7 ? e 7 ? e 7 ? ? ? ? ? e 7 ? ? ? ...
output:
133037
result:
ok answer is '133037'
Test #4:
score: 0
Accepted
time: 131ms
memory: 19428kb
input:
200000 10000 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5...
output:
6786
result:
ok answer is '6786'
Test #5:
score: 0
Accepted
time: 144ms
memory: 19372kb
input:
200000 10000 e 1 s 1 w 1 n 2 e 2 ? w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 ? e 1 s 1 w 1 n 2 e 2 s 2 w 2 ? e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s...
output:
6786
result:
ok answer is '6786'
Test #6:
score: 0
Accepted
time: 119ms
memory: 17180kb
input:
100000 50000 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1...
output:
523
result:
ok answer is '523'
Test #7:
score: -100
Wrong Answer
time: 124ms
memory: 20736kb
input:
200000 4 s 3 e 2 ? n 5 s 2 e 2 e 5 w 2 w 6 w 5 w 2 n 4 e 3 ? n 5 e 4 n 5 ? s 2 w 1 e 4 s 3 ? ? n 1 e 3 w 7 n 5 w 5 e 1 ? w 3 s 6 e 7 e 4 e 5 n 5 w 3 w 7 e 2 s 2 w 2 e 1 s 3 s 4 w 7 n 3 w 6 e 4 s 7 w 5 n 5 ? ? s 2 e 1 s 3 ? s 1 e 6 n 6 e 7 ? s 6 s 3 w 6 w 2 e 7 e 3 w 3 e 6 e 4 n 2 n 7 w 3 s 5 w 7 n 2...
output:
70
result:
wrong answer expected '52', found '70'