QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107571#884. Joining Treasure HuntSortingWA 1146ms59604kbC++203.7kb2023-05-22 01:03:522023-05-22 01:03:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-22 01:03:54]
  • 评测
  • 测评结果:WA
  • 用时:1146ms
  • 内存:59604kb
  • [2023-05-22 01:03:52]
  • 提交

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 ] ;
const int MAXN = 4e5 + 7 ;
bool good[ MAXN ] ;

void solve ( ) {
    cin >> n >> m ;
    a.resize ( n ) , b.resize ( m ) ;
    for ( int i = 0 ; i + ( m - 1 ) < n ; ++ i ) {
        good[ i ] = true ;
    }
    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 < n ; ++ i ) {
        char c ; int x ;
        cin >> c ;
        if ( c == '?' ) { a[ i ] = 0 ; continue ; }
        cin >> x ;
        a[ i ] = ord ( c ) * 8 + x ;
    }
    for ( int i = 0 ; i < m ; ++ i ) {
        char c ; int x ;
        cin >> c ;
        if ( c == '?' ) { b[ i ] = 0 ; continue ; }
        cin >> x ;
        b[ i ] = ord ( c ) * 8 + x ;
    }
    reverse ( b.begin ( ) , b.end ( ) ) ;
    for ( int ctr = 0 ; ctr < 2 ; ++ ctr ) {
        for ( int i = 1 ; i < 50 ; ++ i ) {
            enc[ i ] = rng ( ) % mod + 1 ;
        }

        hh1.resize ( n ) , hh2.resize ( m ) ;
        for ( int i = 0 ; i < n ; ++ i ) {
            hh1[ i ] = ( enc[ a[ i ] ] * enc[ a[ i ] ] ) % mod ;
        }
        for ( int i = 0 ; i < m ; ++ i ) {
            hh2[ i ] = enc[ b[ i ] ] ;
        }
        auto ret1 = conv ( hh1 , hh2 ) ;

        hh3.resize ( n ) , hh4.resize ( m ) ;
        for ( int i = 0 ; i < n ; ++ i ) {
            hh3[ i ] = enc[ a[ i ] ] ;
        }
        for ( int i = 0 ; i < m ; ++ i ) {
            hh4[ i ] = ( enc[ b[ i ] ] * enc[ b[ i ] ] ) % mod ;
        }
        auto ret2 = conv ( hh3 , hh4 ) ;
        for ( int i = 0 ; i + m - 1 < n ; ++ i ) {
            if ( ( ret1[ i + ( m - 1 ) ] - ret2[ i + ( m - 1 ) ] + mod ) % mod != 0 ) {
                good[ i ] = false ;
            }
        }
    }
    int ans = 0 ;
    for ( int i = 0 ; i + m - 1 < n ; ++ i ) {
        ans += good[ i ] ;
    }
    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: 2ms
memory: 3436kb

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: 3512kb

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: 1146ms
memory: 59604kb

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: 224ms
memory: 19904kb

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: 259ms
memory: 19864kb

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: 221ms
memory: 17280kb

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: 224ms
memory: 20960kb

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'