Submission #1274169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274169		jojeonghoon	Painting Squares (IOI20_squares)	C++20	0 / 100	28 ms	524 KiB

squares

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

const int LM=1234, m=1<<9;
vector<int> G[LM], ep;

void dfs(int x){
    while(!G[x].empty()){
        int t=G[x].back();
        G[x].pop_back();
        dfs(t);
    }
    ep.push_back(x);
}

int D[LM];

vector<int> paint(int n){
    vector<int>ret;
    
    for(int i=0; i<m; i++){
        G[i].push_back((i<<1)%m);
        G[i].push_back(((i<<1)+1)%m);
    }
    ep.clear();
    fill(D,D+(1<<10),0);
    dfs(0);
    
    reverse(ep.begin(),ep.end());
    ret.assign(min(9,n), 0);
    
    for(int i=1; i<n-8; i++) ret.push_back(ep[i]%2);
    
    for(int i=0; i<n-10; i++){
        int t=0;
        for(int j=0; j<10; j++) t += ret[i+j]<<j;
        D[t]=i;
    }
    
    ret.push_back(min(10,n));
    
    return ret;
}

int find_location(int n, vector<int>c){
    if(c.back()==-1 || n<10){
        int k=0;
        for(int i:c) k+=i<0;
        return max(n-10, 0)+k;
    }
    
    int t=0;
    for(int i=0; i<10; i++) t+=c[i]<<i;
    return D[t];
}

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