# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
4947 | hana5505 | 탐사 (KOI13_probe) | C++98 | 771 ms | 504 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct pp{
int x, y, r;
};
struct qq{
int x, idx;
};
vector<qq> son;
vector<pp> que, que2, bac;
bool cmp1(struct pp a, struct pp b){
if (a.x == b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(struct pp a, struct pp b){
if (a.y == b.y) return a.x>b.x;
return a.y>b.y;
}
bool cmp3(struct qq a, struct qq b){
if (a.x == b.x) return a.idx<b.idx;
return a.x>b.x;
}
int k, n, is_ans;
void back(int c, int ar[])
{
int i, j, cnt = 0, cnt2 = 0, t = 0;
if (is_ans) return;
if (c == son.size()){
for (i = 1; i <= k; i++){
if (ar[i] == 1) printf("#");
else printf("-");
}
is_ans = 1;
return;
}
if (ar[son[c].idx] != -1) back(c + 1, ar);
ar[son[c].idx] = 1;
for (i = 0; i<bac.size(); i++){
cnt = 0;
cnt2 = 0;
if (bac[i].x <= son[c].idx && son[c].idx <= bac[i].y){
for (j = bac[i].x; j <= bac[i].y; j++){
if (ar[j] == 1) cnt++;
if (ar[j] == -1) cnt2++;
}
if (cnt>bac[i].r){
t = 1;
break;
}
if (cnt + cnt2<bac[i].r){
return;
ar[son[c].idx] = -1;
}
}
else continue;
}
if (!t) back(c + 1, ar);
ar[son[c].idx] = 0;
t = 0;
for (i = 0; i<bac.size(); i++){
cnt = 0;
cnt2 = 0;
if (bac[i].x <= son[c].idx && son[c].idx <= bac[i].y){
for (j = bac[i].x; j <= bac[i].y; j++){
if (ar[j] == 1) cnt++;
if (ar[j] == -1) cnt2++;
}
if (cnt>bac[i].r){
t = 1;
break;
}
if (cnt + cnt2<bac[i].r){
ar[son[c].idx] = -1;
return;
}
}
else continue;
}
if (!t) back(c + 1, ar);
ar[son[c].idx] = -1;
return;
}
int main()
{
pp tmp;
qq tmp2;
int ar[45];
int ct[45];
int i, tx, ty, tr, cnt = 0, j;
scanf("%d %d", &k, &n);
for (i = 1; i <= k; i++) ar[i] = -1;
for (i = 1; i <= n; i++){
scanf("%d %d %d", &tmp.x, &tmp.y, &tmp.r);
que.push_back(tmp);
if (tmp.y - tmp.x + 1<tmp.r){
printf("NONE");
return 0;
}
}
while (1){
cnt = 0;
sort(que.begin(), que.end(), cmp1);
que2.clear();
que2 = que;
que.clear();
tmp.x = que2[0].x;
tmp.y = que2[0].y;
tmp.r = que2[0].r;
que.push_back(tmp);
for (i = 1; i<que2.size(); i++){
if (que2[i - 1].x == que2[i].x){
if (que2[i - 1].y == que2[i].y){
if (que2[i - 1].r != que2[i].r) {
printf("NONE"); return 0;
}
continue;
}
tmp.x = que2[i - 1].y + 1;
tmp.y = que2[i].y;
tmp.r = que2[i].r - que2[i - 1].r;
if (tmp.r<0){
printf("NONE");
return 0;
}
que.push_back(tmp);
cnt++;
}
else{
tmp.x = que2[i].x;
tmp.y = que2[i].y;
tmp.r = que2[i].r;
que.push_back(tmp);
}
}
sort(que.begin(), que.end(), cmp2);
que2.clear();
que2 = que;
que.clear();
tmp.x = que2[0].x;
tmp.y = que2[0].y;
tmp.r = que2[0].r;
que.push_back(tmp);
for (i = 1; i<que2.size(); i++){
if (que2[i - 1].y == que2[i].y){
if (que2[i - 1].x == que2[i].x){
if (que2[i - 1].r != que2[i].r){
printf("NONE");
return 0;
}
continue;
}
tmp.x = que2[i].x;
tmp.y = que2[i - 1].x - 1;
tmp.r = que2[i].r - que2[i - 1].r;
if (tmp.r<0){
printf("NONE");
return 0;
}
que.push_back(tmp);
cnt++;
}
else{
tmp.x = que2[i].x;
tmp.y = que2[i].y;
tmp.r = que2[i].r;
que.push_back(tmp);
}
}
for (i = 1; i <= k; i++) ct[i] = 0;
for (i = 0; i<que.size(); i++){
if ((que[i].y - que[i].x + 1) == que[i].r){
for (j = que[i].x; j <= que[i].y; j++) ar[j] = 1;
}
else if (que[i].r == 0){
for (j = que[i].x; j <= que[i].y; j++) ar[j] = 0;
}
else{
for (j = que[i].x; j <= que[i].y; j++){
if (ar[j] == -1) ct[j]++, ar[j] = -1;
}
bac.push_back(que[i]);
}
}
if (cnt == 0) break;
que.clear();
que = bac;
bac.clear();
}
for (i = 1; i <= k; i++){
tmp2.x = ct[i];
tmp2.idx = i;
son.push_back(tmp2);
}
sort(son.begin(), son.end(), cmp3);
back(0, ar);
if (!is_ans) printf("NONE");
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |