oj.uz

Submission #186612

# Submission time Handle Problem Language Result Execution time Memory
186612 2020-01-12T08:48:10 Z Ruxandra985 Alternating Current (BOI18_alternating) C++14
0 / 100
 3000 ms 1976 KB 
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
pair <int,int> v[DIMN];
int d[DIMN] , cer[DIMN] , f[DIMN] , sol[DIMN];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , j , ok , poz , what;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
        if (v[i].first <= v[i].second){
            for (j = v[i].first ; j <= v[i].second ; j++){
                d[j]++;
            }
        }
        else {
            for (j = v[i].first ; j <= n ; j++){
                d[j]++;
            }
            for (j = 1 ; j <= v[i].second ; j++){
                d[j]++;
            }
        }
    }
    for (j=1;j<=m;j++){

        ok = 0;
        for (i=1;i<=n;i++){
            if (d[i] == 1 && cer[i] < 3 && cer[i] > 0)
                ok = i;
        }

        if (ok){

            for (i=1;i<=m;i++){
                if (!f[i]){ /// inca e relevant
                    if (v[i].first <= v[i].second && v[i].first <= ok && ok <= v[i].second){
                        poz = i;
                        f[i] = 1;
                    }
                    else if (v[i].first > v[i].second && (ok >= v[i].first || ok <= v[i].second)){
                        poz = i;
                        f[i] = 1;
                    }
                }
            }

            what = cer[ok];

        }
        else {
            what = 1;
            for (i=1;i<=m;i++){
                if (!f[i]){
                    poz = i;
                    f[i] = 1;
                    break;
                }
            }
        }
        sol[poz] = what - 1;
        /// update

        for (i=1;i<=n;i++){
            if ((v[poz].first <= v[poz].second && v[poz].first <= i && i <= v[poz].second) ||
                (v[poz].first > v[poz].second && (i >= v[poz].first || i <= v[poz].second))){
                /// i e afectat de interval
                d[i]--;
                if (cer[i] == 0){
                    if (what == 1)
                        cer[i] = 2;
                    else cer[i] = 1;
                }
                else if (cer[i] == 3){}
                else { /// e 1 sau 2 , cere ceva si i se da
                    if (cer[i] == what){
                        cer[i] = 3;
                    }
                }

            }
        }

    }
    for (i=1;i<=n;i++){
        if (cer[i] > 0 && cer[i] < 3){
            fprintf (fout,"impossible");
            return 0;
        }
    }
    for (i=1;i<=m;i++){
        fprintf (fout,"%d",sol[i]);
    }
    return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:11:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
alternating.cpp:13:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:64:18: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
         sol[poz] = what - 1;
         ~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 1 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 0 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Incorrect 1 ms 376 KB no wires in direction 0 between segments 15 and 15
28 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 1 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 0 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Incorrect 1 ms 376 KB no wires in direction 0 between segments 15 and 15
28 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 1 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 0 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Incorrect 1 ms 376 KB no wires in direction 0 between segments 15 and 15
28 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 1976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 1 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 1 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 0 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Incorrect 1 ms 376 KB no wires in direction 0 between segments 15 and 15
28 Halted 0 ms 0 KB -