Submission #1347358

#TimeUsernameProblemLanguageResultExecution timeMemory
1347358MMihalevCookies (JOI23_cookies)C++20
Compilation error
0 ms0 KiB
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
const int MAX_N=3e3+3;

int n,m;
int a[MAX_N];
int b[MAX_N];

bitset<MAX_N>dp[MAX_N][MAX_N],bor[MAX_N];
int minsum[MAX_N];

vector<int>boxes[MAX_N];
vector<int>box;
void constructans()
{
    sort(box.rbegin(),box.rend());
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++)s.insert({a[i],i});
    
    int j=0;
    for(int B:box)
    {
        j++;
        vector<int>curbox;
        for(auto [sz,type]:s)curbox.push_back(type);

        for(int i=1;i<=B;i++)
        {
            boxes[j].push_back(curbox.back());
            s.erase({a[curbox.back()]--,curbox.back()});
            if(a[curbox.back()])s.insert({a[curbox.back()],curbox.back()});
            curbox.pop_back();
        }
    }

    cout<<box.size()<<"\n";
    for(int i=1;i<=box.size();i++)
    {
        cout<<boxes[i].size()<<" ";
        for(int x:boxes[i])cout<<x<<" ";
        cout<<"\n";
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        all+=a[i];
    }

    for(int boxes=1;boxes<=all;boxes++)
    {
        for(int i=1;i<=n;i++)
        {
            minsum[boxes]+=min(boxes,a[i]);
        }
    }

    bor[0][0]=1;
    for(int sum=1;sum<=all;sum++)
    {
        bor[sum][sum]=1;
        bor[sum]|=bor[sum-1];
    }

    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    sort(b+1,b+m+1);
    reverse(b+1,b+m+1);
    
    dp[0][0][0]=1;

    for(int id=1;id<=m;id++)
    {
        for(int boxes=0;boxes<=all;boxes++)
        {
            dp[id][boxes]|=dp[id-1][boxes];
            if(boxes)
            {
                int sm=minsum[boxes]-b[id];
                if(sm>=0)
                {
                    dp[id][boxes]|=(((dp[id][boxes-1])&(bor[sm]))<<b[id]);
                }
            }
            
        }
    }

    int ans=-1;
    for(int boxes=1;boxes<=all;boxes++)
    {
        if(dp[m][boxes][all])
        {
            ans=boxes;
            break;
        }
    }

    if(ans==-1)
    {
        cout<<-1<<"\n";
        return 0;
    }

    int id=m,boxes=ans,sum=all;

    while(boxes)
    {
        if(dp[id][boxes-1][sum-b[id]])
        {
            box.push_back(b[id]);
            boxes--;
            sum-=b[id];
        }
        else id--;
    }

    constructans();

    return 0;
}

Compilation message (stderr)

/tmp/cc4WMP8I.o: in function `constructans()':
cookies.cpp:(.text+0x17f6): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text+0x1845): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text+0x1875): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text+0x18b2): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text+0x1b33): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
/tmp/cc4WMP8I.o: in function `main':
cookies.cpp:(.text.startup+0x13): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
cookies.cpp:(.text.startup+0x39): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text.startup+0x43): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
cookies.cpp:(.text.startup+0x4e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
cookies.cpp:(.text.startup+0x5d): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4WMP8I.o
cookies.cpp:(.text.startup+0x6c): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status