제출 #1169161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169161		pythontest	Painting Squares (IOI20_squares)	C++20	0 / 100	1 ms	420 KiB

squares

#include "squares.h"
#include <vector>
#include <iostream>
std::vector<int> kolejne;
std::vector<int> paint(int n) {
	std::vector<int> labels(n + 1, 1);
    if(kolejne.empty()){
        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++) {
//            std::cerr<<"I: "<<i<<" J: "<<j<<" K: "<<kolejne[i]<<" B: "<<(kolejne[i]&(1<<j))<<'\n';
            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) {
//    for(auto x:c){
//        std::cerr<<x<<" ";
//    }
//    std::cerr<<"\n";
    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;
        }
    }
//    std::cerr<<"F:"<<f<<'\n';
    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);
//    std::cerr<<"BITSONLEFT: "<<bitsonleft<<" LOWPART: "<<lowpart<<" HIGHPART: "<<highpart<<'\n';
    int bn=0;
    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;
//                std::cerr<<"ZNALAZŁEM BLOK: "<<bn<<"\n";
                break;
            }
    }
	return 12*bn-(f+3);
}

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