Submission #2958

#	Time	Username	Problem	Language	Result	Execution time	Memory
2958		ainta	Art Class (IOI13_artclass)	C++98	100 / 100	129 ms	8572 KiB

artclass

#include "artclass.h"
#include <stdio.h>
int C[500][500],count,h,w,RR[500][500],GG[500][500],BB[500][500],X[500],Y[500],O[100][100][100];
int abs(int a){return a<0?-a:a;}
int F(int x,int y,int r,int g,int b){
    return (RR[x][y]-r)*(RR[x][y]-r)+(GG[x][y]-g)*(GG[x][y]-g)+(BB[x][y]-b)*(BB[x][y]-b);
}
bool chk(int x,int y,int r,int g,int b){
    if(x<0||x>=h)return false;
    if(y<0||y>=w)return false;
    if(C[x][y])return false;
    if(F(x,y,r,g,b)<1000)return true;
    return false;
}

void DFS(int x,int y,int r,int g,int b){
    C[x][y]=count;
    if(chk(x-1,y,r,g,b))DFS(x-1,y,r,g,b);
    if(chk(x+1,y,r,g,b))DFS(x+1,y,r,g,b);
    if(chk(x,y-1,r,g,b))DFS(x,y-1,r,g,b);
    if(chk(x,y+1,r,g,b))DFS(x,y+1,r,g,b);
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    h=H,w=W;
    count=0;
    int i,j,c1=0,c2=0,ck1=0,ck2=0,S=0,S2=0,C1=0,C2=0;
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            if(i)S+=abs(R[i][j]-R[i-1][j])+abs(G[i][j]-G[i-1][j])+abs(B[i][j]-B[i-1][j]),C1++;
            if(j)S2+=abs(R[i][j]-R[i][j-1])+abs(G[i][j]-G[i][j-1])+abs(B[i][j]-B[i][j-1]),C2++;
        }
    }
    double K=(S+S2)/(C1+C2);
    if(K<9)return 4;
    if(K>54)return 3;
    if(K>35)return 2;
    if(K<22)return 1;
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            RR[i][j]=R[i][j],GG[i][j]=G[i][j],BB[i][j]=B[i][j];
            O[R[i][j]/10][G[i][j]/10][B[i][j]/10]++;
            C[i][j]=0;
            Y[j]=0;
        }
        X[i]=0;
    }
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            if(!C[i][j]){
                count++;
                DFS(i,j,R[i][j],G[i][j],B[i][j]);
            }
            if(i && C[i][j]!=C[i-1][j])c1++;
            if(j && C[i][j]!=C[i][j-1])c2++;
        }
    }
    c1/=(H-1);
    c2/=(W-1);
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            if(i && C[i][j]!=C[i-1][j])X[i-1]++;
            if(j && C[i][j]!=C[i][j-1])Y[j-1]++;
        }
    }
    for(i=0;i<H-1;i++){
        if(X[i]>c1+(W-1)/2)ck1++;
    }
    for(i=0;i<W-1;i++){
        if(Y[i]>c2+(H-1)/2)ck2++;
    }
    if(ck1&&ck2 && ck1+ck2>2){
        return 1;
    }
    return 2;
}

• Subtask 1: 100 / 100