Submission #1169109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169109		wojtekmal	Painting Squares (IOI20_squares)	C++20	100 / 100	27 ms	540 KiB

squares

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

bool graph_made = false;
array<int, 1024> graph;
array<int, 1024> node_to_cycle;
vector<set<int>> cycles;
array<bool, 1024> visited;
array<int, 1024> node_to_pos;

void make_graph()
{
    graph_made = true;
    for (int i = 512; i < 1024; i++) graph[i] = 1;
    int cycle_count = 0;

    for (int i = 0; i < 1024; i++)
    {
        if (visited[i]) continue;
        set<int> cycle;

        for (int node = i; !visited[node]; node = (node << 1) & 1023 | graph[node])
        {
            visited[node] = true;
            cycle.insert(node);
            node_to_cycle[node] = cycle_count;
        }

        cycles.push_back(cycle);
        cycle_count++;
    }

    for (int i = 0; i < 1024; i++)
    {
        if (node_to_cycle[i] != node_to_cycle[i ^ 512])
        {
            graph[i] ^= 1;
            graph[i ^ 512] ^= 1;
            int new_cycle = node_to_cycle[i];
            int old_cycle = node_to_cycle[i ^ 512];

            for (int node : cycles[old_cycle])
            {
                cycles[new_cycle].insert(node);
                node_to_cycle[node] = new_cycle;
            }
        }
    }

    int pos = 0;

    for (int node = 0; pos < 1024; pos++)
    {
        node_to_pos[node] = pos;
        node = (node << 1) & 1023 | graph[node];
    }
}

vector<int> paint(int n)
{
    if (!graph_made) make_graph();
    vector<int> answer(n + 1);

    int pos = 0;

    for (; pos < 10 && pos < n; pos++) answer[pos] = 0;

    for (int node = 0; pos < n; pos++)
    {
        answer[pos] = graph[node];
        node = (node << 1) & 1023 | graph[node];
    }

    answer[n] = 10;

    return answer;
}

int find_location(int n, vector<int> c)
{
    if (!graph_made) make_graph();

    for (int i = 0; i < 10; i++)
    {
        if (c[i] == -1) return n - i;
    }

    int node = 0;
    for (int i = 0; i < 10; i++) node += c[i] * (1 << (9 - i));
    return node_to_pos[node];
}

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