oj.uz

Submission #681845

# Submission time Handle Problem Language Result Execution time Memory
681845 2023-01-14T16:43:12 Z Vladth11 ZigZag (COCI17_zigzag) C++14
80 / 80
 192 ms 16232 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef pair <int, int> pii;
typedef long long ll;

const int NMAX = 100001;
const int VMAX = 41;
const int INF = 1e9;
const int MOD = 1000000009;
const int BLOCK = 318;
const int base = 31;
const int nrbits = 21;

vector <int> v[2][27];
string s[NMAX];
string org[NMAX];
int indice[27];

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i, maxim = 0;
    cin >> n >> m;
    for(i = 1; i <= n; i++){
        cin >> s[i];
        org[i] = s[i];
      	for(int j = 0; j < s[i].size(); j++) s[i][j]++;
        maxim = max(maxim, (int)s[i].size());
    }
    for(i = 1; i <= n; i++){
        while(s[i].size() < maxim){
            s[i] += 'a';
        }
    }
    maxim--;
    for(i = 1; i <= n; i++)
    v[1 - (maxim%2)][0].push_back(i);
    for(i = maxim; i >= 0; i--){
        int act = i%2;
        int last = 1 - act;
        for(int j = 0; j < 27; j++){
            for(auto x : v[last][j]){
                v[act][s[x][i] - 'a'].push_back(x);
            }
            v[last][j].clear();
        }
    }
    while(m--){
        char c;
        int ind;
        cin >> c;
        ind = c - 'a';
      	ind++;
        cout << org[v[0][ind][indice[ind]]] << "\n";
        indice[ind]++;
        if(indice[ind] == v[0][ind].size()) indice[ind] = 0;
    }
    return 0;
}

Compilation message

zigzag.cpp: In function 'int main()':
zigzag.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |        for(int j = 0; j < s[i].size(); j++) s[i][j]++;
      |                       ~~^~~~~~~~~~~~~
zigzag.cpp:41:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         while(s[i].size() < maxim){
      |               ~~~~~~~~~~~~^~~~~~~
zigzag.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if(indice[ind] == v[0][ind].size()) indice[ind] = 0;
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 192 ms 16108 KB Output is correct
8 Correct 182 ms 16076 KB Output is correct
9 Correct 191 ms 16232 KB Output is correct
10 Correct 187 ms 16232 KB Output is correct