Ois_div3 `Execution killed` da stoll(string) ma meno di 1 MiB in uso

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.

il codice sorgente è:

#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:

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:

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;
}

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.

Almeno per questa riga del codice :

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

accedi a una posizione non valida

1 Mi Piace

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:

    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:

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…

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.

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.

1 Mi Piace

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