Submission #1009408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009408		canadavid1	Robot Contest (IOI23_robot)	C++17	96 / 100	135 ms	9704 KiB

robot

/* colors.txt:
#ffffff 0
#0000ff 1
#ffff00 T
#ff0000 H
#005500 <
#005500 v
#005500 >
#005500 ^
*/
#define return_if(x) do { \
auto v = x;\
if(v.size())return v;\
} while(0)

#include "robot.h"
#include <string>
#include <map>
#include <set>
#include <array>
#include <algorithm>
#include <optional>
#include <iostream>

static std::map<char,std::set<int>> symbols{
    {'0',{0}},
    {' ',{0}},
    {'1',{1}},
    {'T',{2}},
    {'H',{3}},
    {'<',{4}},
    {'v',{5}},
    {'>',{6}},
    {'^',{7}},
    {'#',{-1,-2}},
    {'$',{-2}},
    {'*',{-2,-1,0,1,2,3,4,5,6,7}},
    {'a',{0,4,5,6,7}},
    {'b',{-2,-1,0,4,5,6,7}},
    {'u',{-2,-1,0,2,3,4,5,6,7}},
    {'h',{-2,-1,0,1,2,4,5,6,7}},
    {'t',{-2,-1,0,1,3,4,5,6,7}},
    {'s',{-1,0}}
};
static std::map<int,char> cosymbol = {
    {-2,'$'},
    {-1,'#'},
    {0,'0'},
    {1,'1'},
    {2,'T'},
    {3,'H'},
    {4,'<'},
    {5,'v'},
    {6,'>'},
    {7,'^'},
};
static std::map<int,int> rotate = {
    {4,5}, // <v
    {5,6}, // v>
    {6,7}, // >^
    {7,4}, // ^<
    {'W','S'},
    {'S','E'},
    {'E','N'},
    {'N','W'}
};
static const std::vector<std::string> or_rules = {
"$\
$0*\
 * ^H",
"$\
$1*\
 * 1T",
"*\
>0$\
 $ HW",
"v\
*0$\
 $ HN",
"H\
*T$\
 $ ^N",
"*\
HT$\
 $ <W",
"$\
$T*\
 H vS",
"$\
$TH\
 * >E",
"T\
*H$\
 $ 1N",
"*\
TH$\
 $ 1W",
"$\
$*1\
 * 1T",
"$\
$**\
 1 1T",
};
static const std::vector<std::string> rules = {
"v\
hHT\
 h HN",
"v\
hHh\
 T HN",
"v\
THh\
 h HN",

"H\
*HT\
 * HE",
"H\
*H*\
 T HS",
"H\
TH*\
 * HW",

"H\
tHt\
 t TN",

"H\
hah\
 h HN",
"H\
*T<\
 * ^N",
"H\
*T*\
 ^ ^N",
"H\
>T*\
 * ^N",
"H\
*T*\
 * 0N",
"T\
*H*\
 * TN",
"T\
*T*\
 * HH",
"b\
bv<\
 b >E", // these might include start/end, fix
"b\
bv0\
 b >E",
"b\
bvb\
 b >H",
"v\
*0*\
 * ^N",

"v\
**1\
 * 1N",
"v\
***\
 1 1N",
"v\
1**\
 * 1N",

};

/*
    3,2 slider
    <^>v rooted tree at robot
*/
// curr, west, south, east, north
void rotate_match_string(std::string& s)
{
    std::string rs = "<v>^<";
    for(auto i : {2,1,5,3,0,7})
    {
        auto& v = s[i];
        auto r = rs.find_first_of(v);
        if(r!=rs.npos) v = rs[r+1];
    }
    auto t = s[0];
    s[0] = s[3];
    s[3] = s[5];
    s[5] = s[1];
    s[1] = t;
    rs = "WSENW";
    auto r = rs.find_first_of(s[8]);
    if(r!=rs.npos) s[8] = rs[r+1];
}
std::string match(const std::array<int,5>& S,std::string s,bool oriented)
{
    for(int i = 0; i < 4; i++,rotate_match_string(s))
    {
        if(oriented && i > 0) return "";
        std::array<char,5> sym = {s[2],s[1],s[5],s[3],s[0]};
        bool b = true;
        for(int i = 0; i < 5; i++) 
            if (!symbols[sym[i]].count(S[i])) 
                b = false;
        if(b) return s.substr(7);
    }
    return "";
}
void rotate_state_list(std::array<int,5>& S)
{
    for(int i = 0; i < 5; i++)
    {
        if(rotate.count(S[i])) S[i] = rotate[S[i]];
    }
    std::rotate(S.begin()+1,S.begin()+4,S.end());
}

struct action
{
    std::array<int,5> state;
    int new_state;
    char act;
    action(std::array<int,5> a,int s,char b) : state(a),new_state(s),act(b) {}
};
std::vector<action> gen_all_action(std::string s,bool oriented)
{
    std::vector<action> o;
    for(int i = 0; i < (oriented ? 1 : 4); i++,rotate_match_string(s))
    {
        int symb = *symbols[s[7]].begin();
        char act = s[8];
        std::array<const std::set<int>*,5> poss;
        int ct = 0;
        for(auto i : {2,1,5,3,0}) poss[ct++] = &symbols[s[i]];
        #define foring(i) for(auto c##i : *poss[i])
        foring(0) foring(1) foring(2) foring(3) foring(4)
        o.emplace_back(std::array<int,5>{c0,c1,c2,c3,c4},symb,act);
    }
    return o;
}


void print_s(int* S)
{
    std::cout << " " << cosymbol[S[4]] << "\n"
              << cosymbol[S[1]] << cosymbol[S[0]] << cosymbol[S[3]] << "\n"
              << " " << cosymbol[S[2]] << "\n";
}
std::string get_move(std::array<int,5>);
std::pair<int,char> get_move_rot(std::vector<int> S,int d=5)
{
    // if(d==0) return {-1,0};
    std::array<int,5> S2;
    for(int i = 0; i < 5; i++) S2[i] = S[i];
    // auto[c,w,s,e,n] = S2;
    // if(!(c==7 && w == -2 && s == 0 && e == 0 && n == -2)) continue;
    // if(c==4 && w == -2 && s == 0 && e == 0 && n == -2)
    // {
    //     std::cout << "now\n";
    //     print_s(S2);
    // }
        // print_s(S2.data());
        // std::cout << "\n";
    auto s = get_move(S2);
    if (s!=""){
    
    int new_symbol = s[0];
    char action = s[1];
    new_symbol = *symbols[new_symbol].begin();
    // std::cout << cosymbol[new_symbol] << action << "\n";
    
    // print_s(S2.data());
    // std::cout << new_symbol << " " << action << "\n";
    if(/*false && */d>0 && action=='H')
    {
        S[0] = new_symbol;
        return get_move_rot(S,d-1);
    }
    return {new_symbol,action};
    }
    
    return {-1,0};
}
// curr, west, south, east, north
std::string get_move(std::array<int,5> S)
{
    auto[c,w,s,e,n] = S;

    for(const auto& i : or_rules) return_if(match(S,i,true));
    for(const auto& i : rules) return_if(match(S,i,false));
    
    return "";
    /*
        no 321 nor end:
            if current arrow:
                rotate arrow cw
                if can move there: go there
            else:
                set arrow towards other in-arrow
                go there
            
    
    */
}

void program_pulibot()
{   
    // std::vector<int> S(5);
    // std::cin.tie(0)->sync_with_stdio(false);
    // std::cout << "std::map<std::array<int,5>,std::pair<int,char> = {\n";
    // #define LOOP(i) for (S[i] = -2; S[i] < 8; S[i]++)
    // LOOP(0) LOOP(1) LOOP(2) LOOP(3) LOOP(4)
    // {
    //     if(S[0]<0) continue;
    //     auto[Z,A] = get_move_rot(S);
    //     if(Z!=-1)
    //     {
    //         // std::cout << "{{";
    //         // for(auto i : S)
    //         // {
    //         //     std::cout << i << ",";
    //         // }
    //         // std::cout << "},{" << Z << ",'" << A << "'}},\n";
    //         set_instruction(S,Z,A);
    //     }
            
    // }
    std::set<std::array<int,5>> seen;
    std::vector<int> _s(5);
    for(auto& r : or_rules)
    {
        for(auto[s,z,a] : gen_all_action(r,true))
        {
            if(seen.count(s)) continue;
            seen.insert(s);
            for(int i = 0; i < 5; i++) _s[i] = s[i];
            set_instruction(_s,z,a);
        }
    }
    for(auto& r : rules)
    {
        for(auto[s,z,a] : gen_all_action(r,false))
        {
            if(seen.count(s)) continue;
            seen.insert(s);
            for(int i = 0; i < 5; i++) _s[i] = s[i];
            set_instruction(_s,z,a);
        }
    }
    // std::cout << "};\n";
}

Compilation message (stderr)

robot.cpp: In function 'std::string get_move(std::array<int, 5>)':
robot.cpp:291:9: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  291 |     auto[c,w,s,e,n] = S;
      |         ^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 20 / 20
• Subtask 5: 42.0000000018 / 46