QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226409#7508. Fast DebuggerSolitaryDream#WA 177ms71720kbC++175.4kb2023-10-25 22:30:222023-10-25 22:30:23

Judging History

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

  • [2023-10-25 22:30:23]
  • 评测
  • 测评结果:WA
  • 用时:177ms
  • 内存:71720kb
  • [2023-10-25 22:30:22]
  • 提交

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'