Submission #1068194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068194		Unforgettablepl	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	9 ms	1372 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    vector<int> convert_to_base3(int x) {
        vector<int> ans(8);
        for(int i=0;i<8;i++) {
            ans[i] = x%3;
            x/=3;
        }
        return ans;
    }
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> digits(N+1);
    for(int i=0;i<=N;i++)digits[i]=convert_to_base3(i);
    vector<vector<int>> ans;
    {
        vector<int> curr(N+1);
        curr[0]=1;
        for(int i=1;i<=N;i++) {
            if(digits[i][7]==2)curr[i]=3;
            if(digits[i][7]==1)curr[i]=2;
            else curr[i]=1;
        }
        ans.emplace_back(curr);
    }
    int move = 1;
    for(int bit=7;bit;bit--) {
        vector<int> curr(N+1);
        // If 0 at bit
        curr[0]=move-1;
        for(int i=1;i<=N;i++) {
            if(digits[i][bit]>0)curr[i]=-(move^3);
            else if(digits[i][bit-1]==2)curr[i]=ans.size()+5;
            else if(digits[i][bit-1]==1)curr[i]=ans.size()+4;
            else curr[i]=ans.size()+3;
        }
        ans.emplace_back(curr);
        // If 1 at bit
        curr[0]=move-1;
        for(int i=1;i<=N;i++) {
            if(digits[i][bit]==0)curr[i]=-(move);
            else if(digits[i][bit]==2)curr[i]=-(move^3);
            else if(digits[i][bit-1]==2)curr[i]=ans.size()+4;
            else if(digits[i][bit-1]==1)curr[i]=ans.size()+3;
            else curr[i]=ans.size()+2;
        }
        ans.emplace_back(curr);
        // If 2 at bit
        curr[0]=move-1;
        for(int i=1;i<=N;i++) {
            if(digits[i][bit]<2)curr[i]=-(move);
            else if(digits[i][bit-1]==2)curr[i]=ans.size()+3;
            else if(digits[i][bit-1]==1)curr[i]=ans.size()+2;
            else curr[i]=ans.size()+1;
        }
        ans.emplace_back(curr);
        move^=3;
    }
    for(int&i:ans[ans.size()-1]) {
        if(i==ans.size())i=-(move^3);
        else if(i==ans.size()+2)i=-move;
        else if(i==ans.size()+1)i=ans.size();
    }
    for(int&i:ans[ans.size()-2]) {
        if(i==ans.size())i=-(move^3);
        else if(i==ans.size()+2)i=-move;
        else if(i==ans.size()+1)i=ans.size();
    }
    for(int&i:ans[ans.size()-3]) {
        if(i==ans.size())i=-(move^3);
        else if(i==ans.size()+2)i=-move;
        else if(i==ans.size()+1)i=ans.size();
    }
    vector<int> curr(N+1);
    curr[0]=move-1;
    for(int i=1;i<=N;i++) {
        if(digits[i][0]==2)curr[i]=-(move^3);
        else curr[i]=-move;
    }
    ans.emplace_back(curr);
    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:64:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(i==ans.size())i=-(move^3);
      |            ~^~~~~~~~~~~~
prison.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         else if(i==ans.size()+2)i=-move;
      |                 ~^~~~~~~~~~~~~~
prison.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         else if(i==ans.size()+1)i=ans.size();
      |                 ~^~~~~~~~~~~~~~
prison.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if(i==ans.size())i=-(move^3);
      |            ~^~~~~~~~~~~~
prison.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         else if(i==ans.size()+2)i=-move;
      |                 ~^~~~~~~~~~~~~~
prison.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         else if(i==ans.size()+1)i=ans.size();
      |                 ~^~~~~~~~~~~~~~
prison.cpp:74:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(i==ans.size())i=-(move^3);
      |            ~^~~~~~~~~~~~
prison.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         else if(i==ans.size()+2)i=-move;
      |                 ~^~~~~~~~~~~~~~
prison.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         else if(i==ans.size()+1)i=ans.size();
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 90