QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#343467	#8174. Set Construction	ucup-team004^#	WA	0ms	3840kb	C++20	2.1kb	2024-03-02 16:51:42	2024-03-02 16:51:42

Judging History

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

[2024-03-02 16:51:42]
评测

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

查看

[2024-03-02 16:51:42]
提交

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);
    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(k,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)
                    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: 3572kb

input:

output:

0 1 2 3 7
0 4 5 7 8 12 13 15
0 1152921504606846975

result:

ok AC

Test #2:

score: -100

Wrong Answer

time: 0ms

memory: 3840kb

input:

output:

0 63
0 56 63
0 56 59 63
0 56 57 59 63
0 48 49 51 55 63
0 48 49 51 59 55 63
0 48 49 57 51 59 55 63
0 32 33 49 35 51 39 55 63
0 32 33 49 35 51 59 39 55 63
0 32 33 49 57 35 51 59 39 55 63
0 28 29 31 32 60 61 63 35 51 59 39
0 8 9 13 11 15 32 40 41 45 43 47 39
0 8 9 13 11 15 32 40 41 45 43 47 39 55
0 4 5...

result:

wrong answer (28 AND 39) is not in A