QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #85067 | #5233. Wielki Zderzacz Termionów [A] | anhduc2701 | 0 | 26ms | 26912kb | C++23 | 4.7kb | 2023-03-06 22:20:27 | 2023-03-06 22:20:53 |
Judging History
answer
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "WZT"
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
int inv2;
string s;
int inv[maxn];
int invfact[maxn];
int fact[maxn];
int binpow(int a,int b){
int res=1;
while(b>0){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int calc(int z,int t){
int d=binpow(2,z);
if(z%2==1){
d-=2;
}
else{
d-=1;
}
if(d<0)d+=mod;
if(z%6==0){
if(t==1 || t==2){
return d*inv[3]%mod;
}
else{
return (d*inv[3]+1)%mod;
}
}
else if(z%6==1){
if(t==0 || t==1){
return (d*inv[3]+1)%mod;
}
else{
return d*inv[3]%mod;
}
}
else if(z%6==2){
if(t==0 || t==2){
return d*inv[3]%mod;
}
else{
return (d*inv[3]+1)%mod;
}
}
else if(z%6==3){
if(t==1 || t==2){
return (d*inv[3]+1)%mod;
}
else{
return d*inv[3]%mod;
}
}
else if(z%6==4){
if(t==0 || t==1){
return d*inv[3]%mod;
}
else{
return (d*inv[3]+1)%mod;
}
}
else{// z%6==5
if(t==0 || t==2){
return (d*inv[3]+1)%mod;
}
else{
return d*inv[3]%mod;
}
}
}
int N,C,Z;
int ok=0;
int Z1;
int Z2;
int C1;
int C2;
int so=0;
int calc(){
int q=(((N%3+(Z-C)%3)+6))%3;
if(q==1){
q=2;
}
else if(q==2){
q=1;
}
int ans=binpow(2,N)-calc(N,q);
//cout<<ans<<" ";
if((Z1==n/2+1 && C2==n/2 ) && n%2==1 && n>1){
ans--;
}
if(( C1==n/2+1 && Z2==n/2) && n%2==1 && n>1){
ans--;
}
return (ans%mod+mod)%mod;
}
signed main()
{
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
// freopen(task".inp" , "r" , stdin);
// freopen(task".out" , "w" , stdout);
cin>>n>>m;
cin>>s;
s=' '+s;
inv2=binpow(2,mod-2);
inv[1] =invfact[1]=fact[1]=inv[0]=invfact[0]=fact[0]= 1;
for(int i = 2; i < maxn; ++i){
inv[i] = mod - (mod/i) * inv[mod%i] % mod;
fact[i]= fact[i-1]*i%mod;
invfact[i]=invfact[i-1]*inv[i]%mod;
}
for(int i=1;i<=n;i++){
if(s[i]=='C'){
if(i%2==1){
C1++;
}
else{
C2++;
}
C++;
}
if(s[i]=='Z'){
if(i%2==1){
Z1++;
}
else{
Z2++;
}
Z++;
}
if(s[i]=='N'){
if(i%2==1){
C1++;
}
else{
C2++;
}
if(i%2==1){
Z1++;
}
else{
Z2++;
}
N++;
}
}
for(int i=2;i<=n;i++){
if(s[i]=='C' && s[i-1]=='C'){
so++;
}
if(s[i]=='Z' && s[i-1]=='Z'){
so++;
}
}
cout<<calc()<<"\n";
for(int i=1;i<=m;i++){
int k;
char c;
cin>>k>>c;
if(s[k]=='C'){
if(k%2==1){
C1--;
}
else{
C2--;
}
C--;
}
if(s[k]=='Z'){
if(k%2==1){
Z1--;
}
else{
Z2--;
}
Z--;
}
if(s[k]=='N'){
if(k%2==1){
C1--;
}
else{
C2--;
}
if(k%2==1){
Z1--;
}
else{
Z2--;
}
N--;
}
if(k>1&& s[k]==s[k-1] && s[k]!='N'){
so--;
}
if(s[k]==s[k+1] && s[k]!='N' && k<n){
so--;
}
s[k]=c;
if(k>1&& s[k]==s[k-1] && s[k]!='N'){
so++;
}
if(s[k]==s[k+1] && s[k]!='N' && k<n){
so++;
}
if(s[k]=='C'){
if(k%2==1){
C1++;
}
else{
C2++;
}
C++;
}
if(s[k]=='Z'){
if(k%2==1){
Z1++;
}
else{
Z2++;
}
Z++;
}
if(s[k]=='N'){
if(k%2==1){
C1++;
}
else{
C2++;
}
if(k%2==1){
Z1++;
}
else{
Z2++;
}
N++;
}
cout<<s<<" ";
cout<<calc()<<"\n";
}
return 0;
}
/*
1 1 1 0
2 1 2 1
3 2 3 3
4 5 5 6
5 11 10 11
6 22 21 21
7 43 43 42
8 85 86 85
9 170 171 171
10 341 341 342
11 683 682 683
12 1366 1365 1365
//
// 2^10 /3
// 2^9 * 2/3
// 2^
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 18ms
memory: 26912kb
input:
20 20 CZZCZCCZNCZNZNNCCCZN 10 Z 16 Z 2 C 2 C 2 Z 3 Z 4 C 9 C 6 N 13 N 12 C 8 Z 18 Z 12 C 8 C 5 Z 10 Z 12 Z 9 Z 6 Z
output:
21 CZZCZCCZNZZNZNNCCCZN 21 CZZCZCCZNZZNZNNZCCZN 22 CCZCZCCZNZZNZNNZCCZN 21 CCZCZCCZNZZNZNNZCCZN 21 CZZCZCCZNZZNZNNZCCZN 22 CZZCZCCZNZZNZNNZCCZN 22 CZZCZCCZNZZNZNNZCCZN 22 CZZCZCCZCZZNZNNZCCZN 11 CZZCZNCZCZZNZNNZCCZN 22 CZZCZNCZCZZNNNNZCCZN 43 CZZCZNCZCZZCNNNZCCZN 21 CZZCZNCZCZZCNNNZCCZN ...
result:
wrong answer 2nd lines differ - expected: '21', found: ' CZZCZCCZNZZNZNNCCCZN 21'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 26ms
memory: 26840kb
input:
100 100 ZCZCCCZZNNZNNCCZNNNZZNCCZNNNZNNCNNZCCCZZZNNCNZCCZNNNZNZNNCZCNNZCZZCNCNNZCZCNNZCZCNCZNNCZZNCCNNNZZCZC 8 C 18 C 53 N 52 N 93 C 48 C 67 C 18 Z 57 Z 31 N 94 Z 90 Z 35 C 58 C 20 Z 12 C 87 N 5 C 71 C 21 Z 72 C 38 C 7 N 15 Z 100 Z 58 Z 77 N 87 C 37 Z 26 Z 64 Z 83 N 5 Z 82 C 71 C 37 Z 62 Z 36 N 28 N...
output:
251936682 ZCZCCCZCNNZNNCCZNNNZZNCCZNNNZNNCNNZCCCZZZNNCNZCCZNNNZNZNNCZCNNZCZZCNCNNZCZCNNZCZCNCZNNCZZNCCNNNZZCZC 251936681 ZCZCCCZCNNZNNCCZNCNZZNCCZNNNZNNCNNZCCCZZZNNCNZCCZNNNZNZNNCZCNNZCZZCNCNNZCZCNNZCZCNCZNNCZZNCCNNNZZCZC 625968344 ZCZCCCZCNNZNNCCZNCNZZNCCZNNNZNNCNNZCCCZZZNNCNZCCZNNNNNZNNCZCNNZCZ...
result:
wrong answer 2nd lines differ - expected: '251936681', found: ' ZCZCCCZCNNZNNCCZNNNZZNCCZNNNZ...ZCNCZNNCZZNCCNNNZZCZC 251936681'
Subtask #3:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 23ms
memory: 26884kb
input:
10000 5000 NCZNZCCZCNCZCNCZZCCZCNZNZZNNCCNCZCNZCZCNZCNNZZNZZZNZCCZZZCCNCZNZCCNZCZZCNCZZNNNZCCCZNNZNZCCZNNCNCCCNZNNZCNCCCCZZZNNZNZNCCZCNNZNCCCNNZCNCNNZNCNCZNNCCZCCZNZCNZNCNNNZZNNNCNZNCNNCZCNNZZCCNCZCNNNNZCCNZCCCZZNZZCCZNNNZNNCZZNZZCNCZNNCCNZZCZNNNNCCZCCZCCZCCCZNNCCZZCCZZNCNCCCZNCCCZCZNNNCNNNCNZCCZNZZ...
output:
516850681 NCZNZCCZCNCZCNCZZCCZCNZNZZNNCCNCZCNZCZCNZCNNZZNZZZNZCCZZZCCNCZNZCCNZCZZCNCZZNNNZCCCZNNZNZCCZNNCNCCCNZNNZCNCCCCZZZNNZNZNCCZCNNZNCCCNNZCNCNNZNCNCZNNCCZCCZNZCNZNCNNNZZNNNCNZNCNNCZCNNZZCCNCZCNNNNZCCNZCCCZZNZZCCZNNNZNNCZZNZZCNCZNNCCNZZCZNNNNCCZCCZCCZCCCZNNCCZZCCZZNCNCCCZNCCCZCZNNNCNNNCNZCCZNZZ...
result:
wrong answer 2nd lines differ - expected: '516850681', found: ' NCZNZCCZCNCZCNCZZCCZCNZNZZNNC...ZCZCZCZCCCNZZCNNNZZZN 516850681'
Subtask #4:
score: 0
Output Limit Exceeded
Test #38:
score: 0
Output Limit Exceeded
input:
30000 20000 ZZNNZNNZNNCZNNCCNZCCZZZZZZCZNNCCZCCCZNNNZCZNCCCZCCCNCZZNZCCNCZNNZCNZZZCZCNNCNNZCCNNCCCCCZZNCNZZZCZCCNZNZZNNNCCCZNCCZNNZZCNCCNNNZZZZZNCNNZCZNCZNCCZCZZCNCZNNNCCNZCCCCCCNZNNCZZNCNZNNCZCNCZNCZZNZZNNCZCZCNZZCNNNNZNNZZZNZZNNNNNZCZCNNZZNCZCZCCNCCZZNCCCZZNZZCNNCNZZNNZNCCCZZNCCZCCNZCNCCZCCNNNNCZC...
output:
627728134 ZZNNZNNZNNCZNNCCNZCCZZZZZZCZNNCCZCCCZNNNZCZNCCCZCCCNCZZNZCCNCZNNZCNZZZCZCNNCNNZCCNNCCCCCZZNCNZZZCZCCNZNZZNNNCCCZNCCZNNZZCNCCNNNZZZZZNCNNZCZNCZNCCZCZZCNCZNNNCCNZCCCCCCNZNNCZZNCNZNNCZCNCZNCZZNZZNNCZCZCNZZCNNNNZNNZZZNZZNNNNNZCZCNNZZNCZCZCCNCCZZNCCCZZNZZCNNCNZZNNZNCCCZZNCCZCCNZCNCCZCCNNNNCZCN...
result:
Subtask #5:
score: 0
Output Limit Exceeded
Test #50:
score: 0
Output Limit Exceeded
input:
100000 50000 NNCZNCNCCZCZNCZZNNNNNZCNZCCCZCNCNZNCNZCNCCZZCZZNCZNZZNZCCCCNZNZNNNNNZNNCZNCZCNNZNCCNNZCNZNCNNZNZZCZNNCCCNCNNZCNCNNNNCZNNZNZCZNZZCCZNCCNZCNZZCNNZCNCNZNZNNZZCZZCCCCNCZZNZZCZCZNCNZZZCNNZNZCCZCNCZZNNCCNZNZNNCZCNCCCCNCNZZZZNNNCNZNCNCNCNCCZNCZNCNNZNCCNNNCNZZCZZCNZNZNCNCCZNNNCZCZCCCZCNCNZNCNZC...
output:
760867136 NNCZNCNCCZCZNCZZNNNNNZCNZCCCZCNCNZNCNZCNCCZZCZZNCZNZZNZCCCCNZNZNNNNNZNNCZNCZCNNZNCCNNZCNZNCNNZNZZCZNNCCCNCNNZCNCNNNNCZNNZNZCZNZZCCZNCCNZCNZZCNNZCNCNZNZNNZZCZZCCCCNCZZNZZCZCZNCNZZZCNNZNZCCZCNCZZNNCCNZNZNNCZCNCCCCNCNZZZZNNNCNZNCNCNCNCCZNCZNCNNZNCCNNNCNZZCZZCNZNZNCNCCZNNNCZCZCCCZCNCNZNCNZCZZ...
result:
Subtask #6:
score: 0
Output Limit Exceeded
Test #62:
score: 0
Output Limit Exceeded
input:
200000 100000 ZNCCNZCNCZZZZZZNNNNCNZCCCNNNCCZNCZCCZZNZZCZCZCCCNZCNNNNNCNNCZCZNCCCZZNNZNZZZNCZNNZCNZCCNCZCCZNNZCNCCNZNCNNNNZZNNNZCCCZZNNZCNCNNCZNZZNNZZZCCCCCCNNNNNNCNZCCNCNZCZZNCNCNCCNZCZCCZNNNNZZZNCCCCNNNCNZCCNCCZCZCNCCNCNCZNNNCNZZNNZCZZZNZCZNNNZNZZNNCCCCCCZNCNNNZCNZZCZZNCCZNCNCCCNCCZCNZNZCZNZZCCNCZ...
output:
717427645 ZNCCNZCNCZZZZZZNNNNCNZCCCNNNCCZNCZCCZZNZZCZCZCCCNZCNNNNNCNNCZCZNCCCZZNNZNZZZNCZNNZCNZCCNCZCCZNNZCNCCNZNCNNNNZZNNNZCCCZZNNZCNCNNCZNZZNNZZZCCCCCCNNNNNNCNZCCNCNZCZZNCNCNCCNZCZCCZNNNNZZZNCCCCNNNCNZCCNCCZCZCNCCNCNCZNNNCNZZNNZCZZZNZCZNNNZNZZNNCCCCCCZNCNNNZCNZZCZZNCCZNCNCCCNCCZCNZNZCZNZZCCNCZZCC...
result:
Subtask #7:
score: 0
Output Limit Exceeded
Test #75:
score: 0
Output Limit Exceeded
input:
200000 100000 CCNNCZCNZCCCNCZZNZCCNCNCNNZCZZZCCZCCCCCNCZZNNZNCZNCZZNNCCNZZZZZNNNNZNNCZCNZCZNCNCZZZCNZNZNNCZNNNCCCCNNCZCCNNCZZCNZCNCCZZNZNNCNCCCNNZNNZZNZZCCNNCCZNZCNCNNZNCNNCNZZNZZNNZNNCCNCCNNZCCNZNCNZNCZNCNCNZCCZNCZNNZNNNZNZCCZNCZCZNZZNZCZZZCNCNZZZZZNNZNZZCCNNZNCNNNZNNNNZCNCCCCCCCNZCNCCZZCNNCNZCNZNC...
output:
732326940 CCNNCZCNZCCCNCZZNZCCNCNCNNZCZZZCCZCCCCCNCZZNNZNCZNCZZNNCCNZZZZZNNNNZNNCZCNZCZNCNCZZZCNZNZNNCZNNNCCCCNNCZCCNNCZZCNZCNCCZZNZNNCNCCCNNZNNZZNZZCCNNCCZNZCNCNNZNCNNCNZZNZZNNZNNCCNCCNNZCCNZNCNZNCZNCNCNZCCZNCZNNZNNNZNZCCZNCZCZNZZNZCZZZCNCNZZZZZNNZNZZCCNNZNCNNNZNNNNZCNCCCCCCCNZCNCCZZCNNCNZCNZNCNCC...
result:
Subtask #8:
score: 0
Output Limit Exceeded
Test #85:
score: 0
Output Limit Exceeded
input:
200000 100000 ZZCCCZZCCZNZCZCZNCZCCZCNNNCZZZCNCZCCZCCZNZCCCNNCZZZNCNNCZZNCNCNNCCCZNCNZZCZCNCNCNCZCZCZNNNCNCCCCZNZNZNCCNCCCCNCCZZZNNZCCCCCNZNNZNCCCCZZZZCCNNZZNCNCZNCNCNNNZNZNZNCCNCNZCZCCCNNCCNNZNCNZCCZNZCZCCCZNZCNNCNNZZCCNZNZCZNZCNCCZZNZNCNCZCNNCCCNZNNNCZNNZCZZZCCZCNNZZNZNZCZCCCNNZCZCCCNNZZCZZZNNNZCC...
output:
516190438 ZZCCCZZCCZNZCZCZNCZCCZCNNNCZZZCNCZCCZCCZNZCCCNNCZZZNCNNCZZNCNCNNCCCZNCNZZCZCNCNCNCZCZCZNNNCNCCCCZNZNZNCCNCCCCNCCZZZNNZCCCCCNZNNZNCCCCZZZZCCNNZZNCNCZNCNCNNNZNZNZNCCNCNZCZCCCNNCCNNZNCNZCCZNZCZCCCZNZCNNCNNZZCCNZNZCZNZCNCCZZNZNCNCZCNNCCCNZNNNCZNNZCZZZCCZCNNZZNZNZCZCCCNNZCZCCCNNZZCZZZNNNZCCZCN...
result:
Subtask #9:
score: 0
Output Limit Exceeded
Test #94:
score: 0
Output Limit Exceeded
input:
200000 100000 ZNCZCCCNNCCNCNCZCCZZCNNNNCZCCCZNNCNZNCNCNCZNCZNZNNZNNCCNZZCZZNZZCCNNNZCNNZCZCNCNZNZZNCZNZZNZZNZZZCNCNZNZCNNNCZZNCNZCZNCNNZZCZCCZZZZCZNNNCCCZCNNCNCNCNNCNNCCZNCZZCZZZZCCCZNCCCNCCZCNCCNNZCNNNCCZNCZCZNZCCZNNNZCCCZZZCZCCCZNZCCNNNNZNNCZNCNZNZNCNCCZNCZNZZCZNZNNCCNCNZNZZNCNZCCCNCZZNNNZNNNNZZNC...
output:
423710609 ZNCZCCCNNCCNCNCZCCZZCNNNNCZCCCZNNCNZNCNCNCZNCZNZNNZNNCCNZZCZZNZZCCNNNZCNNZCZCNCNZNZZNCZNZZNZZNZZZCNCNZNZCNNNCZZNCNZCZNCNNZZCZCCZZZZCZNNNCCCZCNNCNCNCNNCNNCCZNCZZCZZZZCCCZNCCCNCCZCNCCNNZCNNNCCZNCZCZNZCCZNNNZCCCZZZCZCCCZNZCCNNNNZNNCZNCNZNZNCNCCZNCZNZZCZNZNNCCNCNZNZZNCNZCCCNCZZNNNZNNNNZZNCNNN...
result:
Subtask #10:
score: 0
Output Limit Exceeded
Test #103:
score: 0
Output Limit Exceeded
input:
200000 100000 CZNCNZZNNNZZNCCZNZCCNNNCZNCNZCCNNCNCCNNZCNZCNCCCCZNZNZNCCNNNNCCNCNZZNZNCZNZZCZNCCNZZCNZNZZCNNNNCZNCCZCZCCCZNNCZZNCZCZNCZNZZNZNCZCZCNNCZCZCCZNZCCNNCCCCZCCNNCNZNCCCNZZZZZZCCZZNCNCZNZZNCZCCZCNZNZZNNNCCCCNZCCZCNZZCNNCCNZZCZZCZZZZZNNZCNCZZZCCCCZCNZZZZNZZZZCCCZZCCNCZNCCZZCNNNCCNZZZCNCZNZCZNC...
output:
83887589 CZNCNZZNNNZZNCCZNZCCNNNCZNCNZCCNNCNCCNNZCNZCNCCCCZNZNZNCCNNNNCCNCNZZNZNCZNZZCZNCCNZZCNZNZZCNNNNCZNCCZCZCCCZNNCZZNCZCZNCZNZZNZNCZCZCNNCZCZCCZNZCCNNCCCCZCCNNCNZNCCCNZZZZZZCCZZNCNCZNZZNCZCCZCNZNZZNNNCCCCNZCCZCNZZCNNCCNZZCZZCZZZZZNNZCNCZZZCCCCZCNZZZZNZZZZCCCZZCCNCZNCCZZCNNNCCNZZZCNCZNZCZNCCCNZ...