fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     ios::sync_with_stdio(false);
  5.     cin.tie(nullptr);
  6.     int n;
  7.     string s;
  8.     if(!(cin>>n>>s)) return 0;
  9.     vector<int> posP, posZ, posM;
  10.     for(int i=0;i<n;i++){
  11.         if(s[i]=='+') posP.push_back(i);
  12.         else if(s[i]=='0') posZ.push_back(i);
  13.         else posM.push_back(i);
  14.     }
  15.     int A=posP.size(), B=posZ.size(), C=posM.size();
  16.     if(B==1){ cout<<-1<<"\n"; return 0; }
  17.     const int INF = 1000000000;
  18.     vector<vector<vector<vector<int>>>> cur(A+1, vector<vector<vector<int>>>(B+1, vector<vector<int>>(C+1)));
  19.     vector<int> init(n, INF);
  20.     cur[0][0][0] = init;
  21.     for(int g=0; g<n; ++g){
  22.         vector<vector<vector<vector<int>>>> nxt(A+1, vector<vector<vector<int>>>(B+1, vector<vector<int>>(C+1)));
  23.         for(int j=0;j<=A;j++){
  24.             for(int t=0;t<=B;t++){
  25.                 for(int k=0;k<=C;k++){
  26.                     if(cur[j][t][k].empty()) continue;
  27.                     vector<int> base = cur[j][t][k];
  28.                     int used = j + t + k;
  29.                     int label = g+1;
  30.                     int parity = (n - used - 1) & 1;
  31.                     if(parity==0){
  32.                         if(j < A){
  33.                             vector<int> nw = base;
  34.                             nw[posP[j]] = label;
  35.                             auto &tar = nxt[j+1][t][k];
  36.                             if(tar.empty() || nw < tar) tar = move(nw);
  37.                         }
  38.                     } else {
  39.                         if(k < C){
  40.                             vector<int> nw = base;
  41.                             nw[posM[k]] = label;
  42.                             auto &tar = nxt[j][t][k+1];
  43.                             if(tar.empty() || nw < tar) tar = move(nw);
  44.                         }
  45.                     }
  46.                     for(int p=2; p<= B - t; ++p){
  47.                         vector<int> nw = base;
  48.                         for(int z=0; z<p; ++z) nw[posZ[t+z]] = label;
  49.                         auto &tar = nxt[j][t+p][k];
  50.                         if(tar.empty() || nw < tar) tar = move(nw);
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.         cur.swap(nxt);
  56.     }
  57.     vector<int> best;
  58.     if(!cur[A][B][C].empty()) best = cur[A][B][C];
  59.     if(best.empty()){ cout<<-1<<"\n"; return 0; }
  60.     for(int i=0;i<n;i++){
  61.         if(i) cout<<' ';
  62.         cout<<best[i];
  63.     }
  64.     cout<<"\n";
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
0-+0
stdout
copy 
-1
https://ideone.com/tzzQ6L
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!