oj.uz

Submission #978804

# Submission time Handle Problem Language Result Execution time Memory
978804 2024-05-09T17:39:09 Z canadavid1 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1628 KB 
#include "prison.h"

#include <vector>
#include <string>
#include <iostream>

std::vector<std::vector<int>> devise_strategy(int N) {
    std::vector<std::vector<std::string>> s{{"+-"}};
    while(s.back().front().size()<N)
    {
        int n = 1;
        while(n<s.size() && s[s.size()-n][0].size()*n <= s[s.size()-n-1][0].size()*(n+1)) n++;
        auto sz = s.size();
        s.emplace_back();
        auto& sn = s.back();
        sn.resize(sz+1);
        const auto& sp = s[s.size()-n-1];
        sn.back() = sp.back().back();
        for(int i = 0; i < n; i++)
        {
            sn.back() += std::string(sp[0].size(),'a'+sz-i-1);
            sn[sz-i-1] = std::string(1+sp.back().size()*i,sp.back()[0]) + sp.back() + std::string(1+sp.back().size()*(n-i-1),sp.back().back());
        }
        sn.back().push_back(sp.back()[0]);
        for(int i = 0; i < sz-n; i++)
        {
            sn[i] = sp[i][0];
            for(int j = 0; j < n; j++) sn[i].append(sp[i]);
            sn[i].push_back(sp[i].back());
        }
    }
    
    
    auto v = std::move(s.back());
    // for(auto& i : v)
    // {
    //     for(int j = 0; j < N; j++)
    //     std::cout << i[j]; std::cout << "\n";
    // }
    std::vector<std::vector<int>> strategy(v.size(),std::vector<int>(N+1));
    char b = 'a'+v.size()-1;
    for(int i = 0; i < v.size(); i++)
    {
        const int j = v.size()-i-1;
        strategy[i][0] = v[j][0]=='+';
        for(int k = 0; k < N; k++)
        {
            switch(v[j][k])
            {
                case '+':
                    strategy[i][k+1] = -2; break;
                case '-':
                    strategy[i][k+1] = -1; break;
                default:
                    strategy[i][k+1] = b-v[j][k];
            }
        }
    }
    // for(auto& i : strategy)
    // {
    //     for(auto n : i) std::cout << n << " ";
    //     std::cout << "\n";
    // }
    
    
    return strategy;
}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:9:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |     while(s.back().front().size()<N)
      |           ~~~~~~~~~~~~~~~~~~~~~~~^~
prison.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         while(n<s.size() && s[s.size()-n][0].size()*n <= s[s.size()-n-1][0].size()*(n+1)) n++;
      |               ~^~~~~~~~~
prison.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   25 |         for(int i = 0; i < sz-n; i++)
      |                        ~~^~~~~~
prison.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 9 ms 1628 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct