Submission #961644

#	Time	Username	Problem	Language	Result	Execution time	Memory
961644		anango	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1364 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N) {
    //cout << "jambloat" << endl;
    int x=20;
    vector<vector<int>> strategy(x+1,vector<int>(N+1,0));
    vector<vector<int>> intervals = {{1,N,0}};//l, r, last dividing state
    vector<int> splits = {3,3,3,3,3,2,2,1,0};
    vector<int> startsplits = {0,1,4,7,10,13,16,18,20};
    //ABBBAAABBBAAABBBAABBA
    vector<int> inspect = {0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0}; //-1=A, -2=B
    assert(inspect.size()==x+1);
    for (int i=0; i<=x; i++) {
        strategy[i][0] = inspect[i];
    }
    for (int split=0; split<splits.size(); split++) {
       /* cout << "splitsize " << split << " " << intervals.size() << endl;
        cout << "INTERVALS" << endl;
        for (auto i:intervals) {
            cout << i[0] <<" " << i[1] << " " << i[2] << endl;
        }*/
        vector<vector<int>> new_intervals;
        for (vector<int> interval:intervals) {
            
            strategy[interval[2]][interval[0]] = -1-inspect[interval[2]]; //so if it starts 1, want to guess -2
            strategy[interval[2]][interval[1]] = inspect[interval[2]]-2; //so if it starts 0, want to guess -2
            if (interval[1]-interval[0] <= 1) {
                continue;
            }
            int delta = (interval[1]-interval[0]-1+splits[split]-1)/splits[split];
            int curl=interval[0]+1;
            int curr=min(curl+delta-1, interval[1]-1);
            for (int divct=0; divct<splits[split]; divct++) {
              
                int xval=startsplits[split+1]+divct;
                //cout << "curinterval "  << curl <<" " << curr << " " << delta << " " << split << endl;
                assert(curr>=curl);
                strategy[xval][interval[0]] = inspect[interval[2]]-2;
                strategy[xval][interval[1]] = -1-inspect[interval[2]];
                new_intervals.push_back({curl, curr, xval});
                for (int cur=curl; cur<=curr; cur++) {
                    strategy[interval[2]][cur] = xval;
                    for (int j=0; j<divct; j++) {
                        strategy[startsplits[split+1]+j][cur] = -1-inspect[interval[2]];//more
                        
                    }
                    for (int j=divct+1; j<splits[split]; j++) {
                        strategy[startsplits[split+1]+j][cur] = inspect[interval[2]]-2;//less
                    }

                }
                curl+=delta;
                curr=min(curl+delta-1, interval[1]-1);

                if (curl>=interval[1]) {
                    break;
                }
            }
        }
        intervals = new_intervals;
    }

    return strategy;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from prison.cpp:2:
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:14:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |     assert(inspect.size()==x+1);
      |            ~~~~~~~~~~~~~~^~~~~
prison.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int split=0; split<splits.size(); split++) {
      |                       ~~~~~^~~~~~~~~~~~~~

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