Submission #1169181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169181		pythontest	Painting Squares (IOI20_squares)	C++17	89 / 100	43 ms	408 KiB

squares

#include "squares.h"
#include <vector>
std::vector<int> paint(int n) {
	std::vector<int> labels(n + 1, 1);
    std::vector<int> kolejne;
    for(int mask=0;mask<(1<<9);mask++){
        if((mask&3)==3||(mask&(1<<8))==(1<<8)) continue;
        bool ok=true;
        for(int t=0;t<6;t++)
            if((mask & (7<<t)) == (7<<t))
                ok=false;
        if(ok)
            kolejne.push_back(mask);
    }
    for(int i=0;12*i<n;i++){
        for(int j=0;j<9&&12*i+j<n;j++) {
            labels[12*i+j]=(kolejne[i]&(1<<j))!=0;
        }
        for(int j=9;j<12&&12*i+j<n;j++) labels[12*i+j]=1;
    }
    labels[n]=14;
    return labels;
}

int find_location(int n, std::vector<int> c) {
    if(*c.rbegin()==-1){
        while(!c.empty()&&*c.rbegin()==-1){
            c.pop_back();
        }
        return n-c.size();
    }
    int f=-1,val=0;
    for (int i = 0; i < 14; i++) {
        val|=(c[i]<<i);
    }
    for(int t=0;t<12;t++){
        if((val&(7<<t))==(7<<t)){
            if((val&(31<<t))==(31<<t)) continue;
            if(t>0&&(val&(7<<(t-1)))==7<<(t-1)&&(val&(7<<(t+1)))!=7<<(t+1)) continue;
            f=t;
        }
    }
    int bitsonleft = std::min(f,9),nadmiarowe = f-bitsonleft;
    int lowpart = (val>>nadmiarowe)&((1<<bitsonleft)-1);
    int highpart = (val>>(f+3))&((1<<(9-bitsonleft))-1);
    int bn=0;
    std::vector<int> kolejne;
    for(int mask=0;mask<(1<<9);mask++){
        if((mask&3)==3||(mask&(1<<8))==(1<<8)) continue;
        bool ok=true;
        for(int t=0;t<6;t++)
            if((mask & (7<<t)) == (7<<t))
                ok=false;
        if(ok)
            kolejne.push_back(mask);
    }
    for(int i=0;i<kolejne.size()-1;i++){
        if(((kolejne[i]>>(9-bitsonleft))&lowpart) == lowpart)
            if((kolejne[i+1]&((1<<(9-bitsonleft))-1))==highpart){
                bn=i+1;
                break;
            }
    }
	return 12*bn-(f+3);
}

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