QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#343474	#8174. Set Construction	ucup-team004^#	WA	0ms	3580kb	C++20	2.2kb	2024-03-02 17:06:04	2024-03-02 17:06:05

Judging History

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

[2024-03-02 17:06:05]
评测

测评结果：WA
用时：0ms
内存：3580kb

查看

[2024-03-02 17:06:04]
提交

answer

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;

vector<ll> calc(int k,int c,int d,int e){
    if(k==3&&e==4)
        return {0,1,2,3,5,7};
    if(k==3&&e==3)
        return {0,1,2,3,7};
    
    vector<ll>ret;
    ret.push_back(0);
    ret.push_back(1);
    --e;
    int u=e/c,v=(e+c-1)/c;
    assert(v<=d);
    ll x=0;
    for(int j=1;j<=1+d-v;++j)
        x+=1ll<<(k-j);
    ret.push_back(x);
    vector<int>dis(c+1);

    for(int i=1;i<=c;++i){
        dis[i]=(e+i-1)/c;
        x+=1ll<<(i-1);
        ll y=x;
        for(int j=1;j<=dis[i];++j){
            ret.push_back(y);
            y+=1ll<<(k-(1+j+d-v));
        }
    }
   // assert(ret.back()==(1ll<<k)-1);
   // cerr<<"!"<<k<<' '<<c<<' '<<d<<' '<<e<<'\n';
   // for(auto i:ret)
   //     cerr<<i<<" ";
   // cerr<<"\n";
    return ret;
}

vector<ll> solve(int n,int m){
    if(m==1ll<<n){
        vector<ll>ret(m);
        iota(ret.begin(),ret.end(),0);
        return ret;
    }
    if(m==2)
        return {0,(1ll<<n)-1};
    if(n==2)
        return {0,1,3};
    for(int i=1;i<n-1;++i){
        int k=n-i+1;
        int c=k/2,d=k-c;
        int e=c*d;
        if(k==3)
            e=4;
        int res=-1;
        if(m<=e+2*(i*(i+1)/2-1))
            res=min((m-1)/2,i*(i+1)/2);
        if(m>2*(1ll<<i)-2 && m <= e + 2*(1ll<<i)-2)
            res=1<<i;
        if(e+2>=m){
            auto v=calc(k,c,d,m-2);
            for(auto&t:v)
                t=(t>>1<<i)+(t&1)*((1ll<<i)-1);
            return v;
        }
        if(res<0)
            continue;
        auto v=solve(i,res);
        int ne=m-2*res+2;
        auto u=calc(k,c,d,ne);
        vector<ll>ret;
        for(auto&t:u)
            if(t&1)
                ret.push_back((t>>1<<i)+(1ll<<i)-1);
            else
                for(auto&s:v)
                    if(s!=(1<<i)-1)
                        ret.push_back((t>>1<<i)+s);
        return ret;
    }
    return {};
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    for(cin>>T; T --> 0; ){
        int n,m;
        cin>>n>>m;
        auto ans=solve(n,m);
        for(int i=0;i<m;++i)
            cout<<ans[i]<<" \n"[i==m-1];
    }
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3580kb

input:

output:

0 1 2 3 7
0 1 2 3 12 13 14 15
0 1152921504606846975

result:

ok AC

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 3580kb

input:

output:

0 63
0 1 60
0 1 56 63
0 1 56 59 63
0 1 56 57 59 63
0 1 48 49 51 55 63
0 1 48 49 51 59 55 63
0 1 48 49 57 51 59 55 63
0 1 32 33 49 35 51 39 55 63
0 1 32 33 49 35 51 59 39 55 63
0 1 2 3 32 33 34 35 51 39 55 63
0 1 2 3 5 7 48 49 50 51 53 55 63
0 1 2 3 5 7 32 33 34 35 37 39 47 63
0 1 2 3 4 5 6 7 56 57 5...

result:

wrong answer 63 is not in A