oj.uz

Submission #4947

# Submission time Handle Problem Language Result Execution time Memory
4947 2014-01-23T13:16:23 Z hana5505 탐사 (KOI13_probe) C++
19 / 19
 771 ms 504 KB 
#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

probe.cpp: In function 'void back(int, int*)':
probe.cpp:30:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (c == son.size()){
         ~~^~~~~~~~~~~~~
probe.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i<bac.size(); i++){
                 ~^~~~~~~~~~~
probe.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i<bac.size(); i++){
                 ~^~~~~~~~~~~
probe.cpp: In function 'int main()':
probe.cpp:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 1; i<que2.size(); i++){
                     ~^~~~~~~~~~~~
probe.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 1; i<que2.size(); i++){
                     ~^~~~~~~~~~~~
probe.cpp:176:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i<que.size(); i++){
                     ~^~~~~~~~~~~
probe.cpp:91:12: warning: unused variable 'tx' [-Wunused-variable]
     int i, tx, ty, tr, cnt = 0, j;
            ^~
probe.cpp:91:16: warning: unused variable 'ty' [-Wunused-variable]
     int i, tx, ty, tr, cnt = 0, j;
                ^~
probe.cpp:91:20: warning: unused variable 'tr' [-Wunused-variable]
     int i, tx, ty, tr, cnt = 0, j;
                    ^~
probe.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
probe.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &tmp.x, &tmp.y, &tmp.r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.47 / 2.47

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 404 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
2.09 / 2.09

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 2 ms 380 KB Output is correct

Subtask #3
1.33 / 1.33

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #4
5.13 / 5.13

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct

Subtask #5
3.61 / 3.61

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 13 ms 376 KB Output is correct

Subtask #6
4.37 / 4.37

# Verdict Execution time Memory Grader output
1 Correct 21 ms 368 KB Output is correct
2 Correct 770 ms 352 KB Output is correct
3 Correct 771 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct