| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 551072 | PiejanVDC | 분수 공원 (IOI21_parks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "parks.h"
using namespace std;
int dx[4] = {2,0,-2,0};
int dy[4] = {0,2,0,-2};
struct S {
int x,y;
int dir;
}s_;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int mxN = (int)2e5 + 5;
int construct_roads(std::vector<int> x, std::vector<int> y) {
const int n = (int)x.size();
map<pair<int,int>,int>mp;
for(int i = 0 ; i < n ; i++)
mp[{x[i],y[i]}] = i;
vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
set<pair<int,int>>processed;
stack<S>s;
s_.x = x[0], s_.y = y[0], s_.dir = 0;
processed.insert({x[0], y[0]});
s.push(s_);
int P = 0;
while(!s.empty()) {
auto node = s.top();
s.pop();
int x = node.x, y = node.y, dir = node.dir;
bool in_order = 0;
if(mp.count({x + dx[dir], y + dy[dir]})) in_order = 0;
int i = dir;
int ii = mp[{x,y}];
int p_ = P;
do {
if(mp.count({x + dx[i], y + dy[i]}) && !processed.count({x + dx[i], y + dy[i]})) {
if(dx[i] == 0) {
if(!processed.count({x-1,y + dy[i]/2}))
a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x+1,y + dy[i]/2}))
a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else {
if(!processed.count({x + dx[i]/2, y-1}))
a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x + dx[i]/2, y+1}))
a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
}
}
if(in_order) i++,i%=4;
else i--, i+=4, i%= 4;
} while(i != dir);
}
if(P < n-1)
return 0;
build(u,v,a,b);
return 1;
}
//#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
using namespace std;
static void check(bool cond, string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
check(!build_called, "build is called more than once");
build_called = true;
m = u.size();
check(int(v.size()) == m, "u.size() != v.size()");
check(int(a.size()) == m, "u.size() != a.size()");
check(int(b.size()) == m, "u.size() != b.size()");
_u = u;
_v = v;
_a = a;
_b = b;
}
int main() {
assert(scanf("%d", &n) == 1);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
build_called = false;
const int possible = construct_roads(x, y);
check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
if (possible == 1) {
check(build_called, "construct_roads() returned 1 without calling build()");
} else {
check(!build_called, "construct_roads() called build() but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
printf("%d\n", m);
for (int j = 0; j < m; j++) {
printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
}
}
fclose(stdout);
return 0;
}