| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 399101 | ACmachine | 미술 수업 (IOI13_artclass) | C++17 | 94 ms | 12068 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};
void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;
template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
// make functions return [0..1]
int style(int h, int w, int R[500][500], int G[500][500], int B[500][500]) {
auto in_tolerance = [&](int a, int b){
return abs(a - b) < 15;
};
auto similar = [&](array<int, 3> a, array<int, 3> b){
return in_tolerance(a[0],b[0]) && in_tolerance(a[1], b[1]) && in_tolerance(a[2], b[2]);
};
vector<vector<array<int, 3>>> grid(500, vector<array<int,3>>(500));
REP(i, h){
REP(j, w){
grid[i][j] = {R[i][j], G[i][j], B[i][j]};
}
}
auto get_green = [&]()->double{
auto is_green = [&](array<double, 3> px)->double{ // high red and green?
double scaling = 1.0 * px[1] / 255.0;
REP(i, 3) px[i] *= scaling;
return max(0.0, 2 * px[1] - px[0] - px[2]);
};
double cnt = 0;
REP(i, h){
REP(j, w){
cnt += is_green({grid[i][j][0], grid[i][j][1], grid[i][j][2]});
}
}
return (double)cnt / (double)(h * w);
};
auto get_granularity = [&]()->double{
double res = 0;
REP(i, h){
REP(j, w){
double curr = 0;
REP(sm, 4){
if(dy[sm] < 0 || dx[sm] < 0) continue;
int ny = i + dy[sm];
int nx = j + dx[sm];
if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
if(!similar(grid[i][j], grid[ny][nx]))
curr+=1.0;
}
res += curr;
}
}
return res / (double)(h * w * 2);
};
auto similar2 = [&](array<int, 3> a, array<int, 3> b){
int cutoff = 40;
return abs(a[0] - b[0]) < cutoff && abs(a[1] - b[1]) < cutoff && abs(a[2] - b[2]) < cutoff;
};
auto get_components = [&]()->array<double, 2>{ // also count disproportionate components
vector<vector<int>> visited(h, vector<int>(w, -1));
int curr_id = 0;
auto bfs = [&](int row, int col){
queue<array<int, 2>> q;
visited[row][col] = curr_id;
q.push({row, col});
while(!q.empty()){
auto v = q.front();
q.pop();
REP(sm, 4){
int ny = v[0] + dy[sm];
int nx = v[1] + dx[sm];
if(ny < 0 || ny >= h || nx < 0 || nx >= w || visited[ny][nx] != -1 || !similar2(grid[ny][nx], grid[row][col]))
continue;
visited[ny][nx] = curr_id;
q.push({ny, nx});
}
}
};
vector<int> miny(h * w, INF);
vector<int> maxy(h * w, -INF);
vector<int> minx(h * w, INF);
vector<int> maxx(h * w, -INF);
vector<int> cnt(h * w, 0);
REP(i, h){
REP(j, w){
if(visited[i][j] == -1){
bfs(i, j);
curr_id++;
}
}
}
REP(i, h){
REP(j, w){
miny[visited[i][j]] = min(miny[visited[i][j]], i);
maxy[visited[i][j]] = max(maxy[visited[i][j]], i);
minx[visited[i][j]] = min(minx[visited[i][j]], j);
maxx[visited[i][j]] = max(maxx[visited[i][j]], j);
cnt[visited[i][j]]++;
}
}
int components = 0; // only 30+ px; ?
int disproportionate_components = 0;
REP(i, h * w){
if(cnt[i] > 10){
components++;
int s = abs(miny[i] - maxy[i]) * abs(minx[i] - maxx[i]);
double cut = 0.3;
if((double)cnt[i] / s < cut)
disproportionate_components++;
}
}
return {(1.0 * components) / (1.0 * h * w), 1.0 * disproportionate_components};
};
double p = get_green();
double p2 = get_granularity();
auto v3 = get_components();
//dbg(p, v3);
if(p2 > 0.25){
if(p2 > 0.5) return 3;
if(v3[1] < 10) return 2;
if(v3[0] > 0.01)
return 3;
else
return 2;
/*
if(p2 > 0.5) return 3;
if(v3[1] < 10) return 2;
if(p < 5) return 3;
*/
}
else{
// 1 or 4
if(v3[0] < 0.001){
return 4;
}
else{
return 1;
}
}
return 2;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||