# Ois\_div3 \`Execution killed\` da stoll(string) ma meno di 1 MiB in uso

**URL:** <https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133>\
**Category:** Aiuto\
**Created:** [26 Marzo 2023, 12:58pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133 "2023-03-26T12:58:37Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [26 Marzo 2023, 12:58pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133/1 "2023-03-26T12:58:37Z")

</div>

Stavo provando div3 dopo non essere riuscito a farlo alle OIS, ma per qualche motivo mi dà _Excecution killed_, pur impiegando meno di 1MiB in tutti i subtask, tranne nell’esempio.

 ![image](https://forum.olinfo.it/uploads/default/original/2X/7/739ab432eff40b29ff8d45622afc8a6f31987bf4.png)

il codice sorgente è:

```auto
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

string toStr(vector<short> V, int except = -1){
  string s;
  char c;
  for(int i: V){
    c = i + '0';
    if(c == -1 + '0'){
      continue;
    }
    s += c;
  }
  return s;
}

string solve(string input){
  vector<short> V;
  set<short> moduli;
  for(char c: input){
    c -= '0';
    moduli.insert(c % 3);
    V.pb(c);
  }
  int modulo_sum = 0;
  for(int i: V){
    modulo_sum += i % 3;
  }
  
  modulo_sum %= 3;
  if(modulo_sum == 0){
    return toStr(V);
  }else{
    int rmd = modulo_sum;
    if(moduli.count(rmd)){
      // prova a rimuovere una sola cifra
      int last = -1;
      for(int i = 0; i<V.size(); i++){
        if((V[i] % 3) == rmd){
          if(V[i] < V[i+1]){
            V[i] = -1;
            return toStr(V, 1);
          }
          last = i;
        }
      }
      assert(last != -1);
      V[last] = -1;
      return toStr(V, 1);
    }else{
      // prova a rimuovere due cifre
      rmd = 3 - rmd;
      if(moduli.count(rmd) >= 2){
        int last1, last2 = -1;
        int rec;
        short lts = 2;

        for(int i = 0; i<V.size(); i++){
          if ((V[i] % 3) == rmd){
            if(V[i] < V[i+1]){
              assert(lts == 1 | lts == 2);
              if(lts == 2){
                rec = i;
                lts --;
              }
              else{
                  V[rec] = -1; V[i] = -1;
                  return toStr(V);
              }
            }
            last1 = last2;
            last2 = i;
          }
        }
        assert(last1 != -1);
        assert(last2 != -1);

        V[last1] = -1;
        V[last2] = -1;

        return toStr(V);
      }
      else{
        return "-1";
      }
    }
  }
}

int main(){
  int N;
  cin >> N;
  string input;
  for(int _ = 0; _ < N; _++){
    cin >> input;
    cout << stoll(solve(input), 0) << endl;
  }
}

```

L’algoritmo per ogni numero in input:

```p
Se è divisibile per 3:
  lo stampa
Se non lo è:
  Se esiste una cifra con modulo uguale al modulo del numero completo:
    elimina dal numero la prima cifra a sinistra minore della seguente con modulo uguale al modulo del numero o se non esiste la prima cifra con modulo uguale al modulo del numero a destra
  Altrimenti se ne esistono 2 cifre con modulo (3 - mod(numero)) compie un procedimento analogo a quello di prima
  Altrimenti stampa -1

```

Ho provato a sostituire stoll con una funzione fatta a mano e in quel caso mi dà semplicemente wrong output:

```auto
ll stollHandmade(string s){
  if(s == "-1") return -1;

  ll num = 0;
  int i = 1;
  for(int d: s){
    assert(!(0 <= d & d <= 9));
    num += (d - '0')*(pow(10, s.size() - i));
    i++;
  }

  if (num) return num;
  else return -1;
}

```

 ![image](https://forum.olinfo.it/uploads/default/original/2X/7/7d8b3429e4ab539de3f5d29fd39053448e40b5b2.png)

Quindi credo sia qualcosa che ha a che fare con stoll(In quanto dopo averlo cambiato sono passato da Excecution killed a Output isn’t correct). Inizialmente pensavo che stoll ricevesse per qualche motivo una stringa non numerica, ma l’assert in stollHandmade mi ha assicurato che non è così (altrimenti avrei ottenuto Excecution killed). Quindi non so più cosa potrebbe essere. Grazie Mille.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [26 Marzo 2023, 4:00pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133/2 "2023-03-26T16:00:14Z")

</div>

Almeno per questa riga del codice :

```
        if(V[i] < V[i+1]){}

```

accedi a una posizione non valida

---

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [26 Marzo 2023, 5:26pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133/3 "2023-03-26T17:26:18Z")

</div>

Grazie!

Ho provato ad aggiungere un controllo `if(i+1 < V.size())` che blocchi l’esecuzione di tutto ciò che sta dentro a `if(V[i] < V[i+1]){...}` sia nel caso della rimozione di due che di una cifra. Purtoppo però non funziona comunque.

Ho provato a sostituire `stoll(string)` con un ciclo che rimuova semplicemente i “leading zeros” dal numero:

```auto
    string s = solve(input);
    
    bool foundNonZero = false;
    for(char c: s){
        if(foundNonZero) cout << c;
        else{
            if(c != '0'){
                foundNonZero = true;
                cout << c;
            }
        }
    }
    if(! foundNonZero) cout << "-1";
    cout << "\n";
  }

```

E in questo caso succede qualcosa di ancora più “strano”: nel subtask d’esempio funziona come al solito, ma nel 5° subtask ne fa 4 giusti:

 ![image](https://forum.olinfo.it/uploads/default/original/2X/f/f93fb8db74f0267c6e046210c26ddaafa6912067.png)

Ma il resto del codice è rimasto invariato(funziona uguale anche senza `if(i+1 < V.size())`). Non capisco perchè con questo codice, stoll e stollHandmade ottengo tre risultati diversi, quando dovrebbero fare la stessa cosa…

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [26 Marzo 2023, 9:01pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133/4 "2023-03-26T21:01:15Z")

</div>

Ciao, sicuramente `stoll` non poteva funzionare visto che la risposta può essere ben sopra i limiti di un `long long`. Non ho letto troppo attentamente il tuo codice ma credo che con questo input dia una risposta sbagliata.

```auto
1
1000003222

```

Anche se non è strettamente problematico ti consiglio di evitare di usare `short` se non è strettamente necessario per stare nel limite di memoria. In questo caso i tuoi dati potrebbero stare anche in un `signed char`, ma conviene usare gli `int` e basta.

---

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [28 Marzo 2023, 1:04pm UTC](https://forum.olinfo.it/t/ois-div3-execution-killed-da-stoll-string-ma-meno-di-1-mib-in-uso/8133/5 "2023-03-28T13:04:05Z")

</div>

Ho capito, in certi casi rimuovere una sola cifra è peggio di rimuoverne due!  
Grazie mille!