oj.uz

Submission #25876

# Submission time Handle Problem Language Result Execution time Memory
25876 2017-06-24T16:17:39 Z model_code Take-out (POI13_usu) C++11
100 / 100
 343 ms 30056 KB 
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Usuwanka                                      *
 *   Autor:                Maciej Matraszek                              *
 *   Zlozonosc czasowa:    O(n log k)                                    *
 *   Zlozonosc pamieciowa: O(n)                                          *
 *   Opis:                 Rozwiazanie weryfikujace                      *
 *                         Buduje kolejne ruchy w zachlanny sposob       *
 *                                                                       *
 *************************************************************************/

#include <cassert>
#include <algorithm>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;


typedef vector<int> Wybor;

stack< int > stosB;         // stos nieuzytych liter b
stack< Wybor > stosWyborow; // stos tworzonych wyborow
int n, k;
char lit;

vector< Wybor > wyjscie;

/*
 * Funkcja sprawdza, czy ostatni wybor jest pelny
 * i jesli tak, to go zapisuje i usuwa ze stosu
 */
bool checkPopSave() {

    if ( (int) stosWyborow.top().size() != k+1 )
        return false;

    wyjscie.push_back(stosWyborow.top());
    stosWyborow.pop();
    return true;
}


int main() {
    cin >> n >> k;

    for(int i=1; i<=n; ++i) {
        cin >> lit;

        if (lit == 'c' ) {
            stosWyborow.push(Wybor());

            // dokladamy do wyboru wolne litery 'b' z lewej
            while((int) stosWyborow.top().size() < k && !stosB.empty()) {
                stosWyborow.top().push_back( stosB.top() );
                stosB.pop();
            }
            stosWyborow.top().push_back(i);
            checkPopSave();

        } else {
            if ( stosWyborow.empty() ) {
                stosB.push(i);
            } else {
                stosWyborow.top().push_back(i);
                checkPopSave();
            }
        }
    }


    for(int r=n/(k+1)-1; r>=0; --r) {
        sort(wyjscie[r].begin(), wyjscie[r].end());

        for(int i=0; i<k+1; ++i)
            cout << wyjscie[r][i]  << " ";

        cout << "\n";
    }

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2168 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3956 KB Output is correct
2 Correct 23 ms 3064 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3992 KB Output is correct
2 Correct 59 ms 3372 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4480 KB Output is correct
2 Correct 73 ms 3504 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 5708 KB Output is correct
2 Correct 149 ms 6612 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 30056 KB Output is correct
2 Correct 229 ms 10112 KB Output is correct
3 Correct 279 ms 6252 KB Output is correct
4 Correct 239 ms 7116 KB Output is correct