act like gold medal IOIer Descrizione del problema Tommaso ha N N oggetti e M M cestini…
- User
act like gold medal IOIer
Descrizione del problema Tommaso ha N N oggetti e M M cestini in camera. Ogni oggetto è rappresentato da una lettera dell'alfabeto maiuscola, da A A a Z Z. I cestini sono numerati da 0 0 a M − 1 M−1. Ogni cestino ha una capacità illimitata e vi è un ordine fra gli elementi al suo interno: l'elemento in posizione 0 0 è sul fondo, quello in posizione 1 1 si trova subito sopra, e così via.
"Alcuni dei cestini di Tommaso"
Inizialmente, tutti gli oggetti si trovano in ordine nel cestino 0 0, e il loro ordine è dato da una stringa S S di lunghezza N N. Il primo carattere di S S rappresenta l'oggetto in posizione 0 0, e così via. Tuttavia, quando è annoiato, Tommaso passa il tempo spostando gli oggetti fra i cestini! In particolare, sposta l'oggetto dalla cima di un cestino alla cima di un altro cestino.
Aiuta Tommaso a tenere traccia degli oggetti nella sua camera, stando sempre pronto a dirgli qual è l'oggetto in una certa posizione di un certo cestino, gestendo i suoi Q Q spostamenti e domande.
Dati di input La prima riga del file di input contiene un intero T T, il numero di casi di test. Seguono T T casi di test, numerati da 1 1 a T T. Ogni caso di test è preceduto da una riga vuota.
Ogni caso di test è composto come segue:
la prima riga contiene gli interi N N, M M e Q Q; la seconda riga contiene la stringa S S; le Q Q righe successive contengono la descrizione di uno spostamento o di un controllo: s a a b b indica uno spostamento: l'oggetto in cima al cestino a a è stato spostato in cima al cestino b b (è garantito che il cestino a a contiene almeno un oggetto al momento dello spostamento); c a a b b indica un controllo: Tommaso vuole sapere qual è il b b-esimo oggetto dal fondo nel cestino a a (è garantito che il cestino a a contiene almeno b + 1 b+1 oggetti al momento del controllo). Dati di output Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:
Case #t: ans ... dove t è il numero del caso di test (a partire da 1
- e ans è una stringa che rappresenta le risposte ai controlli di Tommaso. L' i i-esimo carattere della stringa è una lettera maiuscola che rappresenta la risposta all' i i-esimo controllo.
Assunzioni T
10 T=10, nei file di input che scaricherai saranno presenti esattamente 10 10 casi di test. 2 ≤ N ≤ 300 000 2≤N≤300000. 2 ≤ M ≤ 500 000 2≤M≤500000. 1 ≤ Q ≤ 300 000 1≤Q≤300000. La stringa S S ha lunghezza N N ed è costituita da lettere maiuscole dell'alfabeto inglese. 0 ≤ a , b < M 0≤a,b<M, a ≠ b a =b per ogni spostamento. Per ogni spostamento, c'è almeno un oggetto nel cestino a a. 0 ≤ a < M 0≤a<M, 0 ≤ b < N 0≤b<N per ogni controllo. Per ogni controllo, il cestino a a contiene almeno b + 1 b+1 oggetti. Esempi di input/output Input:
2
3 3 2 ABC s 0 1 c 1 0
4 3 6 BCBA s 0 1 c 1 0 s 0 2 s 1 2 c 2 1 c 0 0 Output:
Case #1: C Case #2: AAB
i want u to act as the most skilled competetive programmer, u take time to think and check if ur solution works and match up with the example tescase, u need to think thoroughly since u r in a contest. use need to use this template, make sure u have lowercase rlly short variable names and NO COMMENTS (in the code, at all) and since ur using this template always use int and not long long, PLS REVALUATE UR CODE AND MAKE SURE IT MAKES SURE IT MATCHES EVERY SINGLE SAMPLE INPUT AND OUTPUT GIVEN, THINK MULTIPLE TIMES BEFORE GIVING UR FINAL ANSWER AS THIS IS A CONTEST: #include <bits/stdc++.h> #define int long long using namespace std;
signed main() { cin.tie(0); ios_base::sync_with_stdio(false); }
- Assistant
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int T; cin >> T; while(T--){ // Skip potential empty lines string tmp; while(getline(cin, tmp)){ if(tmp.empty()) continue; else break; } // Now tmp has N M Q or is empty if(tmp.empty()){ cin >> tmp; } int N, M, Q; if(sscanf(tmp.c_str(), "%lld %lld %lld", &N, &M, &Q)!=3){ cin >> N >> M >> Q; } string S; cin >> S; vector<string> bins(M, ""); bins[0] = S; string ans = ""; for(int i=0;i<Q;i++){ char c; cin >> c; if(c=='s'){ int a, b; cin >> a >> b; char ch = bins[a].back(); bins[a].pop_back(); bins[b].push_back(ch); } else{ int a, b; cin >> a >> b; ans += bins[a][b]; } } static int tc=1; cout << "Case #" << tc++ << ": " << ans << "\n"; } }