Submission #575554

#	Time	Username	Problem	Language	Result	Execution time	Memory
575554		nghiass001	Painting Squares (IOI20_squares)	C++17	100 / 100	202 ms	756 KiB

squares

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define MASK(i) (1LL << (i))
using namespace std;
const int N = 10;
int visited[1 << N], biject[1 << N];
vector<int> nums;

void DFS(int u) {
    while (visited[u] < 2) {
        int tmp = visited[u];
        DFS((u >> 1) | (visited[u]++ << 8));
    }
    nums.push_back(u & 1);
}

void creates() {
    nums.clear();
    nums.assign(9, 0);
    fill(visited, visited + MASK(N), 0);
    DFS(0);
    int number = 0;
    REP(i, 0, MASK(N)) {
        number = (number >> 1) | (nums[i] << 9);
        biject[number] = i - 9;
    }
}

vector<int> paint(int n) {
    vector<int> ans(n + 1);
    creates();

    REP(i, 0, n) ans[i] = nums[i];
    ans[n] = 10;
    return ans;
}

int find_location(int n, vector<int> c) {
    creates();
    int number = 0;
    REP(i, 0, c.size()) {
        if (c[i] == -1) return n - i;
        number = (number >> 1) | (c[i] << 9);
    }
    return biject[number];
}

Compilation message (stderr)

squares.cpp: In function 'void DFS(int)':
squares.cpp:14:13: warning: unused variable 'tmp' [-Wunused-variable]
   14 |         int tmp = visited[u];
      |             ^~~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
squares.cpp:44:5: note: in expansion of macro 'REP'
   44 |     REP(i, 0, c.size()) {
      |     ^~~

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