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.     int A=0,B=0,C=0;
  10.     for(char c:s){ if(c=='+') A++; else if(c=='0') B++; else C++; }
  11.     if(B==1){ cout<<-1<<"\n"; return 0; }
  12.     const int N=55;
  13.     vector<vector<vector<string>>> dp(A+1, vector<vector<string>>(B+1, vector<string>(C+1, "")));
  14.     dp[0][0][0] = "";
  15.     for(int sum=0; sum<n; ++sum){
  16.         for(int j=min(sum,A); j>=0; --j){
  17.             for(int t=min(sum-j,B); t>=0; --t){
  18.                 int k = sum - j - t;
  19.                 if(k<0 || k> C) continue;
  20.                 string cur = dp[j][t][k];
  21.                 if(cur=="") continue;
  22.                 int used = j+t+k;
  23.                 if(used != sum) continue;
  24.                 if((used%2==0) && j+1<=A){
  25.                     string &to = dp[j+1][t][k];
  26.                     string cand = cur + '+';
  27.                     if(to=="" || cand < to) to = cand;
  28.                 }
  29.                 if((used%2==1) && k+1<=C){
  30.                     string &to = dp[j][t][k+1];
  31.                     string cand = cur + '-';
  32.                     if(to=="" || cand < to) to = cand;
  33.                 }
  34.                 for(int p=2; p<=B - t; ++p){
  35.                     string &to = dp[j][t+p][k];
  36.                     string cand = cur + string(p,'0');
  37.                     if(to=="" || cand < to) to = cand;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     string best = dp[A][B][C];
  43.     if(best==""){ cout<<-1<<"\n"; return 0; }
  44.     vector<int> posPlus, posZero, posMinus;
  45.     for(int i=0;i<n;i++){
  46.         if(s[i]=='+') posPlus.push_back(i);
  47.         else if(s[i]=='0') posZero.push_back(i);
  48.         else posMinus.push_back(i);
  49.     }
  50.     vector<int> idxPlus( posPlus.size() ), idxZero(posZero.size()), idxMinus(posMinus.size());
  51.     iota(idxPlus.begin(), idxPlus.end(), 0);
  52.     iota(idxZero.begin(), idxZero.end(), 0);
  53.     iota(idxMinus.begin(), idxMinus.end(), 0);
  54.     vector<int> a(n,0);
  55.     int pP=0,pZ=0,pM=0;
  56.     int curVal=1;
  57.     for(size_t i=0;i<best.size();){
  58.         char c = best[i];
  59.         if(c=='+' || c=='-'){
  60.             int chosen=-1;
  61.             if(c=='+'){ chosen = posPlus[pP++]; }
  62.             else { chosen = posMinus[pM++]; }
  63.             a[chosen]=curVal++;
  64.             i++;
  65.         } else {
  66.             int j=i;
  67.             while(j<best.size() && best[j]=='0') j++;
  68.             int block = j - i;
  69.             vector<int> chosenIdx;
  70.             for(int t=0;t<block;t++){
  71.                 chosenIdx.push_back(posZero[pZ++]);
  72.             }
  73.             sort(chosenIdx.begin(), chosenIdx.end());
  74.             for(int x: chosenIdx) a[x]=curVal;
  75.             curVal++;
  76.             i = j;
  77.         }
  78.     }
  79.     for(int i=0;i<n;i++){
  80.         if(i) cout<<' ';
  81.         cout<<a[i];
  82.     }
  83.     cout<<"\n";
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4
0-+0
stdout
copy 
-1
https://ideone.com/Z1DWf0
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!