Submission #1013870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013870		huutuan	Art Class (IOI13_artclass)	C++14	100 / 100	56 ms	10068 KiB

artclass

#include "artclass.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(69420);

int rand(int l, int r){
   return uniform_int_distribution<int>(l, r)(rng);
}

int H, W, R[500][500], G[500][500], B[500][500];

bool similar(int u, int v, int x, int y, int d){
   return abs(R[u][v]-R[x][y])<=d && abs(G[u][v]-G[x][y])<=d && abs(B[u][v]-B[x][y])<=d;
}

const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
int vis[500][500];

int bfs(int tu, int tv){
   int sz=0;
   queue<pair<int, int>> q;
   q.emplace(tu, tv); vis[tu][tv]=1;
   while (q.size()){
      ++sz;
      int x=q.front().first, y=q.front().second; q.pop();
      for (int i=0; i<4; ++i){
         int u=x+dx[i], v=y+dy[i];
         if (u<1 || v<1 || u>H || v>W || vis[u][v] || !similar(u, v, x, y, 30)) continue;
         q.emplace(u, v); vis[u][v]=1;
      }
   }
   return sz;
}

int style(int _H, int _W, int _R[500][500], int _G[500][500], int _B[500][500]) {
   H=_H, W=_W;
   memcpy(R, _R, sizeof R);
   memcpy(G, _G, sizeof G);
   memcpy(B, _B, sizeof B);
   int cnt=0;
   // for (int _=0; _<500; ++_){
   //    int x=rand(0, H-30), y=rand(0, W-100);
   //    bool check=1;
   //    for (int i=x; i<x+30; ++i) for (int j=y; j<y+100; ++j){
   //       check&=similar(i, j, x, y);
   //    }
   //    cnt+=check;
   // }
   // if (cnt>=100){
   //    return 4;
   // }
   // int cnt2=0;
   // for (int i=0; i<H; ++i) for (int j=0; j<W; ++j) cnt2+=(R[i][j]<=10 || R[i][j]>=245) && (G[i][j]<=10 || G[i][j]<=245) && (B[i][j]<=10 || B[i][j]>=245);
   // cout << cnt2 << ' ';
   // int cnt0=0, cnt1=0, cnt2=0, cnt3=0;
   {
      for (int _=0; _<500; ++_){
         int x=rand(0, H-30), y=rand(0, W-30);
         bool check=1;
         for (int i=x; i<x+30; ++i) for (int j=y; j<y+30; ++j){
            check&=similar(i, j, x, y, 30);
         }
         cnt+=check;
      }
   }
   vector<int> cc;
   for (int i=0; i<H; ++i) for (int j=0; j<W; ++j) if (!vis[i][j]){
      // ++cc;
      int tmp=bfs(i, j);
      if (tmp>100) cc.push_back(tmp);
   }
   // cout << cc.size() << ' ';
   // sort(cc.rbegin(), cc.rend());
   // for (int i:cc) cout << i << ' ';
   if (cnt>=30){
      if ((int)cc.size()<=3) return 4;
      return 1;
      vector<pair<int, int>> v;
      for (int i=0; i<H; ++i) for (int j=0; j<W; ++j){
         bool check=0;
         for (auto &k:v) if (similar(k.first, k.second, i, j, 30)) check=1;
         if (!check) v.emplace_back(i, j);
      }
      // cout << v.size() << ' ';
      if (v.size()<=30) return 4;
      return 1;
   }
   if ((int)cc.size()>=10) return 3;
   return 2;
   // cnt=0;
   // for (int i=0; i<H-1; ++i) for (int j=0; j<W; ++j){
   //    cnt+=similar(i, j, i+1, j, 30);
   // }
   // for (int i=0; i<H; ++i) for (int j=0; j<W-1; ++j){
   //    cnt+=similar(i, j, i, j+1, 30);
   // }
   // cout << cnt << ' ';
   // if (cnt>=2e5) return 2;
   // return 3;
}

• Subtask 1: 100 / 100