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.