Submission #1168373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168373		SmuggingSpun	Painting Squares (IOI20_squares)	C++20	100 / 100	357 ms	464 KiB

squares

#include "squares.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>get_euler(){
    vector<vector<int>>g(512);
    for(int i = 0; i < 512; i++){
        int j = (i << 1) & 511;
        g[i].emplace_back(j);
        g[i].emplace_back(j | 1);
    }
    vector<int>path;
    stack<int>st;
    st.push(0);
    while(!st.empty()){
        int u = st.top();
        if(g[u].empty()){
           path.emplace_back(u & 1);
           st.pop();
        }
        else{
            st.push(g[u].back());
            g[u].pop_back();
        }
    }
    for(int i = 0; i < 9; i++){
        path.emplace_back(0);
    }
    return path;
}
vector<int>paint(int n){
    vector<int>ans = get_euler();
    while(ans.size() > n){
        ans.pop_back();
    }
    ans.emplace_back(10);
    return ans;
}
int find_location(int n, vector<int>c){
    if(c[9] == -1){
        for(int i = 0; i < 9; i++){
            if(c[i] == -1){
                return n - i;
            }
        }
        return n - 9;
    }
    vector<int>euler = get_euler();
    int ans = 0;
    while(true){
        bool flag = true;
        for(int j = 0; j < 10; j++){
            if(euler[ans + j] != c[j]){
                flag = false;
                break;
            }
        }
        if(flag){
            break;
        }
        ans++;
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55