제출 #1013833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013833		huutuan	미술 수업 (IOI13_artclass)	C++14	73 / 100	76 ms	10064 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];

void bfs(int tu, int tv){
   queue<pair<int, int>> q;
   q.emplace(tu, tv); vis[tu][tv]=1;
   while (q.size()){
      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;
      }
   }
}

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/2-30), y=rand(0, W/2-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);
         }
         cnt0+=check;
      }
   }
   {
      for (int _=0; _<500; ++_){
         int x=rand(0, H/2-30), y=rand(W/2, 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);
         }
         cnt1+=check;
      }
   }
   {
      for (int _=0; _<500; ++_){
         int x=rand(H/2, H-30), y=rand(0, W/2-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);
         }
         cnt2+=check;
      }
   }
   {
      for (int _=0; _<500; ++_){
         int x=rand(H/2, H-30), y=rand(W/2, 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);
         }
         cnt3+=check;
      }
   }
   int cc=0;
   for (int i=0; i<H; ++i) for (int j=0; j<W; ++j) if (!vis[i][j]) ++cc, bfs(i, j);
   // cout << cnt0 << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3 << ' ';
   cnt=(!!cnt0)+(!!cnt1)+(!!cnt2)+(!!cnt3);
   if (cnt>=3){
      if (cc<=1000) 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 (cc>=5000) 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: 73 / 100