Submission #17179

#TimeUsernameProblemLanguageResultExecution timeMemory
17179erdemkirazArt Class (IOI13_artclass)C++98
96 / 100
470 ms21264 KiB
#include "artclass.h" #include <bits/stdc++.h> using namespace std; #define type(x) __typeof((x).begin()) #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++) typedef long long ll; typedef pair < int, int > ii; const int inf = 1e9 + 333; const ll linf = 1e18 + inf; const int N = 500; int n, m, r[N][N], g[N][N], b[N][N]; ii root[N][N]; ii f(int x, int y) { if(root[x][y] == ii(0, 0) or root[x][y] == ii(x, y)) return ii(x, y); return root[x][y] = f(root[x][y].first, root[x][y].second); } void road(int x1, int y1, int x2, int y2, int A, int B, int C, int x = 0) { bool flag = 0; if(x2 < n and y2 < m) { flag = 1; flag &= abs(r[x1][y1] - r[x2][y2]) <= A; flag &= abs(g[x1][y1] - g[x2][y2]) <= B; flag &= abs(b[x1][y1] - b[x2][y2]) <= C; if(x) { flag &= g[x1][y1] >= r[x2][y2] - x; flag &= g[x1][y1] >= b[x2][y2] - x; } } if(flag) { int X1 = f(x1, y1).first; int Y1 = f(x1, y1).second; int X2 = f(x2, y2).first; int Y2 = f(x2, y2).second; root[X1][Y1] = ii(X2, Y2); } } bool h[N][N]; int style(int n, int m, int R[500][500], int G[500][500], int B[500][500]) { :: n = n; :: m = m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { r[i][j] = R[i][j]; g[i][j] = G[i][j]; b[i][j] = B[i][j]; } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { road(i, j, i, j + 1, 20, 20, 20); road(i, j, i + 1, j, 20, 20, 20); } } set < ii > cntr; multiset < ii > cntrMul; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cntr.insert(f(i, j)); cntrMul.insert(f(i, j)); } } //printf("cntr.size() %d\n", (int) cntr.size()); if(cntr.size() <= 50) return 4; int bigs = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = f(i, j).first; int y = f(i, j).second; if(!h[x][y]) { h[x][y] = 1; if(cntrMul.count(ii(x, y)) >= 1000) { bigs++; } } } } if(bigs < 4 and cntr.size() <= 100) return 4; //printf("n = %d m = %d\n", n, m); //printf("bigs = %d\n", bigs); //printf("cntr = %d\n", (int) cntr.size()); if(cntr.size() <= 5000 and bigs >= 5) return 1; if(bigs > 2 and bigs * 1200 >= cntr.size()) return 1; cntr.clear(); cntrMul.clear(); memset(root, 0, sizeof(root)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { road(i, j, i, j + 1, 20, 50, 50, 0); road(i, j, i + 1, j, 20, 50, 50, 0); } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cntr.insert(f(i, j)); cntrMul.insert(f(i, j)); } } memset(h, 0, sizeof(h)); bigs = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = f(i, j).first; int y = f(i, j).second; if(!h[x][y]) { h[x][y] = 1; if(cntrMul.count(ii(x, y)) >= 600) { bigs++; } } } } //printf("bigs = %d\n", bigs); //printf("%d\n", (int) cntr.size()); if(cntr.size() <= 9000) return 2; return 3; }

Compilation message (stderr)

artclass.cpp: In function 'int style(int, int, int (*)[500], int (*)[500], int (*)[500])':
artclass.cpp:95:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(bigs > 2 and bigs * 1200 >= cntr.size())
                  ~~~~~~~~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...