QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226425 | #7508. Fast Debugger | SolitaryDream# | WA | 186ms | 71580kb | C++17 | 5.4kb | 2023-10-25 22:48:56 | 2023-10-25 22:48:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
using perm=vector<int>;
const int N=1e5+1e3+7,LIM=2e9;
int n,q;
int cnt;
perm operator *(const perm &a,const perm &b)
{
perm ret(16);
for(int i=0;i<16;i++)
ret[i]=b[a[i]];
return ret;
}
perm qpow(perm a,int b)
{
perm ret(16);
for(int i=0;i<16;i++)
ret[i]=i;
while(b)
{
if(b&1)
ret=ret*a;
b>>=1;
a=a*a;
}
return ret;
}
int fa[N];
vector<int> g[N],pre[N];
vector<perm> pf[N][8];
int r[N],rep[N];
perm f[N][8];
int opt(string s,int x,int y)
{
if(s[0]=='x')
return x^y;
if(s[0]=='a')
return x&y;
return x|y;
}
vector<int> dfs(int x)
{
for(auto v:g[x])
{
if(r[v]>=LIM)
{
auto s=dfs(v);
while(g[x].back()!=v)
g[x].pop_back();
g[x].pop_back();
for(auto p:s)
g[x].push_back(p);
vector<int>().swap(g[v]);
break;
}
}
return g[x];
}
perm res[8];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
int x=0;
rep[0]=1;
for(int i=0;i<8;i++)
{
f[0][i].resize(16);
for(int j=0;j<16;j++)
f[0][i][j]=j;
}
for(int R=1;R<=n;R++)
{
string s;
cin>>s;
if(s=="repeat")
{
++cnt;
int y=cnt;
cin>>rep[y];
g[x].push_back(y);
fa[y]=x;
x=y;
for(int i=0;i<8;i++)
{
f[x][i].resize(16);
for(int j=0;j<16;j++)
f[x][i][j]=j;
}
}
else if(s=="end")
{
int y=fa[x];
r[y]=min(r[y]+r[x]*rep[x],LIM);
for(int i=0;i<8;i++)
f[y][i]=f[y][i]*qpow(f[x][i],rep[x]);
x=y;
}
else if(s.back()=='i')
{
++cnt;
int y=cnt;
fa[y]=x;
g[x].push_back(y);
r[x]++;
r[x]=min(r[x],LIM);
r[y]=1;
rep[y]=1;
string op1;
int op2;
cin>>op1>>op2;
for(int t=0;t<8;t++)
{
f[y][t].resize(16);
for(int i=0;i<16;i++)
{
int o=i;
int j=op1[0]-'a';
int x=o>>j&1;
o^=(x<<j);
x=opt(s,x,op2>>t&1);
o^=(x<<j);
f[y][t][i]=o;
}
}
for(int i=0;i<8;i++)
f[x][i]=f[x][i]*f[y][i];
}
else
{
++cnt;
int y=cnt;
fa[y]=x;
g[x].push_back(y);
r[x]++;
r[x]=min(r[x],LIM);
r[y]=1;
rep[y]=1;
string op1,op2;
cin>>op1>>op2;
for(int t=0;t<8;t++)
{
f[y][t].resize(16);
for(int i=0;i<16;i++)
{
int o=i;
int j1=op1[0]-'a';
int j2=op2[0]-'a';
int A=(o>>j1&1),B=(o>>j2&1);
o^=A<<j1;
A=opt(s,A,B);
o^=A<<j1;
f[y][t][i]=o;
}
}
for(int i=0;i<8;i++)
f[x][i]=f[x][i]*f[y][i];
}
}
dfs(0);
for(int i=0;i<n;i++)
{
if(!g[i].size())
continue;
pre[i].resize(g[i].size());
for(int j=0;j<8;j++)
{
pf[i][j].resize(g[i].size());
for(auto &x:pf[i][j])
{
x.resize(16);
for(int t=0;t<16;t++)
x[t]=t;
}
}
pre[i][0]=r[g[i][0]]*rep[g[i][0]];
for(int j=0;j<8;j++)
pf[i][j][0]=f[g[i][0]][j];
for(int j=1;j<g[i].size();j++)
{
pre[i][j]=pre[i][j-1]+r[g[i][j]]*rep[g[i][j]];
for(int t=0;t<8;t++)
pf[i][t][j]=pf[i][t][j-1]*qpow(f[g[i][j]][t],rep[g[i][j]]);
}
}
while(q--)
{
int k,v[4],nv[4]={0,0,0,0};
cin>>k>>v[0]>>v[1]>>v[2]>>v[3];
for(int i=0;i<8;i++)
{
res[i].resize(16);
for(int j=0;j<16;j++)
res[i][j]=j;
}
int x=0;
while(k)
{
int t=k/pre[x].back();
for(int i=0;i<8;i++)
res[i]=res[i]*qpow(f[x][i],t);
k%=pre[x].back();
if(!k)
break;
int p=upper_bound(pre[x].begin(),pre[x].end(),k)-pre[x].begin();
if(p)
{
for(int i=0;i<8;i++)
res[i]=res[i]*pf[x][i][p-1];
k-=pre[x][p-1];
}
x=g[x][p];
}
for(int i=0;i<8;i++)
{
int o=0;
for(int j=3;j>=0;j--)
o=(o*2+(v[j]>>i&1));
o=res[i][o];
for(int j=0;j<4;j++)
nv[j]+=(o>>j&1)<<i;
}
for(int i=0;i<4;i++)
cout<<nv[i]<<" \n"[i+1==4];
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 48352kb
input:
6 2 repeat 5 xor ax bx xori ax 3 and cx ax xor cx dx end 10 1 2 4 3 8 4 1 2 3
output:
0 2 2 3 4 1 3 3
result:
ok 8 numbers
Test #2:
score: -100
Wrong Answer
time: 186ms
memory: 71580kb
input:
11982 10000 repeat 2 repeat 2 andi bx 201 xori cx 241 repeat 4 xor cx bx xor ax dx repeat 8 or dx bx xori dx 22 end repeat 2 xor dx bx xor dx bx repeat 7 xor bx bx or cx dx and bx cx end andi dx 33 xori ax 179 xori bx 56 end xori dx 63 xori cx 91 xori dx 228 or cx dx repeat 6 xor cx dx xori bx 198 x...
output:
24 195 0 75 0 195 0 245 199 193 6 13 252 73 245 67 0 0 0 0 51 0 0 245 113 52 121 214 51 195 0 75 247 253 247 37 119 198 119 186 235 235 44 36 4 0 181 0 76 228 253 0 51 245 245 33 119 119 176 0 198 198 1 11 199 93 154 3 106 106 152 21 93 92 42 3 236 236 247 147 198 198 204 135 0 51 0 75 119 118 10 15...
result:
wrong answer 25th numbers differ - expected: '99', found: '113'