Submission #978804

#	Time	Username	Problem	Language	Result	Execution time	Memory
978804		canadavid1	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1628 KiB

prison

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90