QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226409 | #7508. Fast Debugger | SolitaryDream# | WA | 177ms | 71720kb | C++17 | 5.4kb | 2023-10-25 22:30:22 | 2023-10-25 22:30:23 |
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[x]=min(r[x]*rep[x],LIM);
r[y]=min(r[y]+r[x],LIM);
for(int i=0;i<8;i++)
f[y][i]=f[y][i]*f[x][i];
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;
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;
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]];
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]];
for(int t=0;t<8;t++)
pf[i][t][j]=pf[i][t][j-1]*f[g[i][j]][t];
}
}
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];
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 48648kb
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: 177ms
memory: 71720kb
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 190 0 195 0 187 119 117 2 173 248 10 181 71 0 61 0 0 51 0 0 187 51 176 191 157 51 195 0 113 78 110 78 7 230 220 230 51 252 252 57 166 4 0 181 0 8 228 189 0 51 0 0 33 213 213 56 33 214 214 136 128 109 229 136 30 243 243 3 153 229 228 56 30 102 102 212 49 117 117 156 183 0 51 0 139 127 126 16...
result:
wrong answer 4th numbers differ - expected: '75', found: '190'