Submission #1009622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009622		canadavid1	Robot Contest (IOI23_robot)	C++17	6 / 100	95 ms	7108 KiB

robot

/* colors.txt:
#ffffff 0
#0000ff 1
#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}},
    {'<',{2}},
    {'v',{3}},
    {'>',{4}},
    {'^',{5}},
    {'#',{-1,-2}},
    {'$',{-2}},
    {'*',{-2,-1,0,1,2,3,4,5}},
    {'a',{0,4,5,6,7}},
    {'b',{-2,-1,0,2,3,4,5}},
    {'s',{-1,0}},
};
static std::map<int,char> cosymbol = {
    {-2,'$'},
    {-1,'#'},
    {0,'0'},
    {1,'1'},
    {2,'<'},
    {3,'v'},
    {4,'>'},
    {5,'^'},
};
static std::map<int,int> rotate = {
    {2,3}, // <v
    {3,4}, // v>
    {4,5}, // >^
    {5,2}, // ^<
    {'W','S'},
    {'S','E'},
    {'E','N'},
    {'N','W'}
};
static const std::vector<std::string> or_rules = {
"$\
$00\
 0 >E",
"$\
$0#\
 0 vS",
"v\
*0$\
 $ >N",
"*\
>0$\
 $ >W",
"$\
$><\
 0 vS",
"$\
$>*\
 0 1E",
"$\
$v<\
 ^ >E",
"$\
$v*\
 ^ vS",
"$\
$v*\
 * 1S",
"1\
**$\
 $ 1T",
"*\
1*$\
 $ 1T",
};
static const std::vector<std::string> rules = {
"1\
*>*\
 ^ >S",
"1\
>>*\
 * >W",
"1\
*>*\
 * 1E",
"*\
1>*\
 ^ >S",
"*\
1>*\
 * 1E",
"*\
*>*\
 1 1E",
"v\
*^<\
 * >E",
"v\
*^0\
 * >E",
"*\
><<\
 * >E",
"*\
><0\
 * >E",
"*\
*v<\
 ^ >E",
"*\
*v0\
 ^ >E",
"v\
*^*\
 * ^N",
"*\
>0*\
 * <W",
"v\
*>*\
 * >N",
"v\
*v*\
 * vN",
"v\
*<*\
 * <N",
"*\
*^*\
 * 0N",

};

/*
    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:266:9: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  266 |     auto[c,w,s,e,n] = S;
      |         ^~~~~~~~~~~

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