Submission #71458

#	Time	Username	Problem	Language	Result	Execution time	Memory
71458		tamtam	Art Class (IOI13_artclass)	C++14	100 / 100	171 ms	52556 KiB

artclass

#include "artclass.h"
#include<cstdio>
#include<queue>
using namespace std;

struct col
{
    double r, g, b;
    col(){}
    col(double r, double g, double b): r(r), g(g), b(b) {}
};

inline double dist2(col &c1, col &c2)
{
    return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b);
}

int n, m;

col a[500][500];
bool chk[500][500];

int dx[8]={-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8]={-1, 0, 1, 1, 1, 0, -1, -1};

int flood(int x, int y)
{
    int ret=0;
    queue<pair<int, int> > q;
    q.push(make_pair(x, y)); chk[x][y]=true;
    while(!q.empty())
    {
        ret++;
        pair<int, int> cur=q.front(); q.pop();
        int cx=cur.first, cy=cur.second;
        for(int k=0;k<8;k++)
        {
            int nx=cx+dx[k], ny=cy+dy[k];
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            if(chk[nx][ny]) continue;
            if(dist2(a[cx][cy], a[nx][ny])<=300)
            {
                chk[nx][ny]=true;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return ret;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    n=H; m=W;
    int i, j, k;
    for(i=0;i<n;i++) for(j=0;j<m;j++) a[i][j]=col(R[i][j],G[i][j],B[i][j]);

    // criterion for style 3: measure noise
    int cnt=0;
    double vartot=0.0;
    for(i=1;i<n-1;i++) for(j=1;j<m-1;j++) for(k=0;k<8;k++)
    {
        int nx=i+dx[k], ny=j+dy[k];
        vartot+=dist2(a[i][j], a[nx][ny]);
        cnt++;
    }
    double crit3=vartot/cnt;
    if(crit3>3000) return 3;
    
    // style 4: measure noise for x and y direction and compare magnitude
    double xntot=0.0, yntot=0.0;
    int xncnt=0, yncnt=0;
    for(i=n/10;i<n*9/10;i++) for(j=m/10;j<m*9/10;j++)
    {
        if(i<n-1){xntot+=dist2(a[i][j], a[i+1][j]); xncnt++;}
        if(j<m-1){yntot+=dist2(a[i][j], a[i][j+1]); yncnt++;}
    }
    xntot/=xncnt; yntot/=yncnt;
    double crit4=max(xntot, yntot)/min(xntot, yntot);
    if(crit4>2.0) return 4;

    // style 2: measure how "green" the picture is
    cnt=0;
    double ngtot=0.0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        double penalty;
        if(a[i][j].g>=60) penalty=0;
        else penalty=(60-a[i][j].g)*(60-a[i][j].g);
        ngtot+=(a[i][j].r*a[i][j].r+a[i][j].b*a[i][j].b)+penalty;
        cnt++;
    }
    double crit2=ngtot/cnt;
    if(10000<crit2 && crit2<33000) return 2;
    
    // style 4 again: number of "areas" is small
    cnt=0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        if(chk[i][j]) continue;
        int area=flood(i, j);
        if(area>10) cnt++;
    }
    if(cnt<10) return 4;

    // style 1 (can be improved): colors consist of white, black, red, blue, yellow,
    //                            and two misc. colors observed from the samples
    const int r=7;
    col vib[r];
    vib[0]=col(255,0,0);
    vib[1]=col(255,255,255);
    vib[2]=col(0,0,0);
    vib[3]=col(0,0,255);
    vib[4]=col(255,255,0);
    vib[5]=col(190,190,190);
    vib[6]=col(180,180,210);
    cnt=0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        double mdist=dist2(vib[0], a[i][j]);
        for(k=1;k<r;k++) mdist=min(mdist, dist2(vib[k], a[i][j]));
        if(mdist<=2500) cnt++;
    }
    double crit1=(double)(cnt)/(n*m);
    if(crit1>0.3) return 1;

    // misc. criteria
    if(crit3>2000) return 3; // not that noisy but fairly so
    if(crit1<0.05) return 4; // more likely to be of type 4 than 1
    return 1; // give up and return 1, for which the criterion wasn't good enough anyway
}

• Subtask 1: 100 / 100