Submission #1147454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147454		Hamed_Ghaffari	Cookies (JOI23_cookies)	C++20	13 / 100	16 ms	1156 KiB

cookies

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

using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back

const int MXN = 503;
const int inf = 1e9;

int n, m, A[MXN], B[MXN], dis[MXN], par[MXN];
bool good[1<<15], vis[15], have[MXN];
int DP[1<<15], PAR[1<<15];

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n;
  assert(n<=500);
  for(int i=0; i<n; i++) cin >> A[i];
  cin >> m;
  for(int i=0; i<m; i++) cin >> B[i], have[B[i]]=1;
  if(m==1) {
    int b = B[0];
    vector<vector<int>> ans;
    priority_queue<pii> pq;
    for(int i=0; i<n; i++) pq.push(pii(A[i],i));
    while(SZ(pq)>=b) {
      vector<int> vec;
      for(int i=0; i<b; i++) {
        vec.pb(pq.top().Y); pq.pop();
      }
      ans.pb(vec);
      for(int i : vec) if(A[i]>1) pq.push(pii(--A[i], i));
    }
    if(!pq.empty()) {
      cout << "-1\n";
      return 0;
    }
    cout << SZ(ans) << '\n';
    for(auto i : ans) {
      cout << SZ(i) << ' ';
      for(auto j : i) cout << j+1 << ' ';
      cout << '\n';
    }
  }
  else if(*max_element(A, A+n)==1) {
    for(int i=1; i<=n; i++) dis[i] = inf;
    queue<int> q;
    q.push(0);
    while(SZ(q)) {
      int v = q.front(); q.pop();
      for(int i=0; i<m; i++)
        if(v+B[i]<=n && dis[v+B[i]]>dis[v]+1) {
          dis[v+B[i]] = dis[v]+1;
          par[v+B[i]] = v;
          q.push(v+B[i]);
        }
    }
    if(dis[n]==inf) {
      cout << "-1\n";
      return 0;
    }
    cout << dis[n] << '\n';
    int v=n;
    int ptr=1;
    while(v) {
      cout << v-par[v] << ' ';
      for(int i=0; i<v-par[v]; i++)
        cout << (ptr++) << ' ';
      cout << '\n';
      v = par[v];
    }
  }
  else {
    int sum=0;
    for(int i=0; i<n; i++) sum += A[i];
    assert(sum<=15);
    vector<int> vec;
    for(int i=0; i<n; i++)
      for(int j=0; j<A[i]; j++)
        vec.pb(i);
    for(int msk=0; msk<(1<<SZ(vec)); msk++) {
      DP[msk] = 1e9;
      good[msk] = 1;
      for(int i=0; i<SZ(vec); i++)
        if(msk>>i&1) {
          if(vis[vec[i]]) good[msk] = 0;
          vis[vec[i]] = 1;
        }
      for(int i=0; i<SZ(vec); i++)
        vis[vec[i]]=0;
    }
    DP[0] = 0;
    for(int msk=1; msk<(1<<SZ(vec)); msk++) {
      for(int smsk=msk; smsk; smsk = (smsk-1)&msk) if(good[smsk] && have[__builtin_popcount(msk)]){
        if(DP[msk^smsk]+1<DP[msk]) {
          DP[msk] = DP[msk^smsk]+1;
          PAR[msk] = msk^smsk;
        }
      }
    }
    int res = DP[(1<<SZ(vec))-1];
    if(res==inf) {
      cout << "-1\n";
      return 0;
    }
    cout << res << '\n';
    int msk = (1<<SZ(vec))-1;
    while(msk) {
      cout << __builtin_popcount(msk^PAR[msk]) << ' ';
      for(int i=0; i<SZ(vec); i++)
        if((msk^PAR[msk])>>i&1)
          cout << vec[i]+1 << ' ';
      cout << '\n';
      msk = PAR[msk];
    }
  }
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 45
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15