fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vi = vector<int>;
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int n;
  8.     string s;
  9.     if(!(cin>>n>>s)) return 0;
  10.     vector<int> posP, posZ, posM;
  11.     for(int i=0;i<n;i++){
  12.         if(s[i]=='+') posP.push_back(i);
  13.         else if(s[i]=='0') posZ.push_back(i);
  14.         else posM.push_back(i);
  15.     }
  16.     int A = posP.size(), B = posZ.size(), C = posM.size();
  17.     if(B==1){ cout << -1 << '\n'; return 0; }
  18.     vi init(n, INT_MAX);
  19.     auto lexmin = [&](const vi &a, const vi &b)->bool{
  20.         if(a.empty()) return false;
  21.         if(b.empty()) return true;
  22.         return a < b;
  23.     };
  24.     struct Key{int j,t,k;};
  25.     auto keyid = [&](int j,int t,int k){ return j*(B+1)*(C+1) + t*(C+1) + k; };
  26.     int layerSize = (A+1)*(B+1)*(C+1);
  27.     vector<unordered_map<int,vi>> dp(n+1);
  28.     dp[0][ keyid(0,0,0) ] = init;
  29.     for(int i=0;i<n;i++){
  30.         for(auto &entry : dp[i]){
  31.             int id = entry.first;
  32.             vi cur = entry.second;
  33.             int tmp = id;
  34.             int k = tmp % (C+1); tmp /= (C+1);
  35.             int t = tmp % (B+1);
  36.             int j = tmp / (B+1);
  37.             int used = j + t + k;
  38.             int label = i + 1;
  39.             if(used % 2 == 0){
  40.                 if(j < A){
  41.                     int nj=j+1, nt=t, nk=k;
  42.                     vi nw = cur;
  43.                     nw[posP[j]] = label;
  44.                     int nid = keyid(nj,nt,nk);
  45.                     auto it = dp[i+1].find(nid);
  46.                     if(it==dp[i+1].end() || nw < it->second) dp[i+1][nid] = nw;
  47.                 }
  48.             } else {
  49.                 if(k < C){
  50.                     int nj=j, nt=t, nk=k+1;
  51.                     vi nw = cur;
  52.                     nw[posM[k]] = label;
  53.                     int nid = keyid(nj,nt,nk);
  54.                     auto it = dp[i+1].find(nid);
  55.                     if(it==dp[i+1].end() || nw < it->second) dp[i+1][nid] = nw;
  56.                 }
  57.             }
  58.             for(int p=2; p<=B - t; ++p){
  59.                 int nj=j, nt=t+p, nk=k;
  60.                 vi nw = cur;
  61.                 for(int z=0; z<p; ++z) nw[posZ[t+z]] = label;
  62.                 int nid = keyid(nj,nt,nk);
  63.                 auto it = dp[i+1].find(nid);
  64.                 if(it==dp[i+1].end() || nw < it->second) dp[i+1][nid] = nw;
  65.             }
  66.         }
  67.     }
  68.     vi ans;
  69.     for(int i=1;i<=n;i++){
  70.         int id = keyid(A,B,C);
  71.         auto it = dp[i].find(id);
  72.         if(it==dp[i].end()) continue;
  73.         if(ans.empty() || it->second < ans) ans = it->second;
  74.     }
  75.     if(ans.empty()){ cout << -1 << '\n'; return 0; }
  76.     for(int i=0;i<n;i++){
  77.         if(i) cout << ' ';
  78.         cout << ans[i];
  79.     }
  80.     cout << '\n';
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
4
0-+0
stdout
copy 
1 3 2 1
https://ideone.com/LVCMgJ
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!