oj.uz

답안 #182405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
182405 2020-01-09T17:34:51 Z Ruxandra985 Plus Minus (BOI17_plusminus) C++14
100 / 100
 583 ms 17784 KB 
#include <bits/stdc++.h>
#define DIMN 100010
#define MOD 1000000007
using namespace std;
int n , m , k , unk;
map <int,int> f , par_plus , par_minus ,par_plus_c , par_minus_c;
int x[DIMN] , s[DIMN] , y[DIMN];
int check (){
    int i;
    /// vezi reseturi
    f.clear();
    par_plus.clear();
    par_minus.clear();
    unk = n;
    for (i=1;i<=k;i++){ /// vrei ca liniile sa fie alternante

        if (!f[x[i]]){
            f[x[i]] = 1;
            unk--;
        }

        if (s[i] == 1){
            if (par_plus[x[i]] == 0){ /// nu ai fixat , e prima oara cand accesezi lin
                par_plus[x[i]] = 1 + y[i] % 2;
            }
            else {
                if (par_plus[x[i]] - 1 != y[i]%2){
                    return 0; /// incerci sa pui un plus prost
                }
            }

        }
        else {
            if (par_minus[x[i]] == 0){ /// nu ai fixat , e prima oara cand accesezi lin
                par_minus[x[i]] = 1 + y[i] % 2;
            }
            else {
                if (par_minus[x[i]] - 1 != y[i]%2){
                    return 0; /// incerci sa pui un plus prost
                }
            }
        }
        if (par_plus[x[i]] && par_minus[x[i]] && par_plus[x[i]] == par_minus[x[i]])
            return 0;

    }
    return 1;
}
int both (){
    int i;
    /// vezi reseturi
    par_plus.clear();
    par_minus.clear();
    for (i=1;i<=k;i++){ /// vrei ca liniile sa fie alternante

        if (s[i] == 1){
            if (par_plus[x[i] % 2] == 0){ /// nu ai fixat , e prima oara cand accesezi lin
                par_plus[x[i] % 2] = 1 + y[i] % 2;
            }
            else {
                if (par_plus[x[i] % 2] - 1 != y[i]%2){
                    return 0; /// incerci sa pui un plus prost
                }
            }

        }
        else {
            if (par_minus[x[i] % 2] == 0){ /// nu ai fixat , e prima oara cand accesezi lin
                par_minus[x[i] % 2] = 1 + y[i] % 2;
            }
            else {
                if (par_minus[x[i] % 2] - 1 != y[i]%2){
                    return 0; /// incerci sa pui un plus prost
                }
            }
        }
        if (par_plus[x[i] % 2] && par_minus[x[i] % 2] && par_plus[x[i] % 2] == par_minus[x[i] % 2])
            return 0;

    }
    return 1;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , sum = 0 , ok = 0;
    char c;
    fscanf (fin,"%d%d%d\n",&n,&m,&k);
    for (i=1;i<=k;i++){
        c = fgetc (fin);
        if (c == '-')
            s[i] = -1;
        else s[i] = 1;
        fscanf (fin,"%d%d\n",&x[i],&y[i]);
    }
    /// verifica daca linia poate fi alternanta

    if (check()){
        int nr = 1;
        int aux = 2;
        while (unk){
            if (unk % 2)
                nr = ((long long)nr * aux)%MOD;
            aux = ((long long)aux * aux)%MOD;
            unk/=2;
        }
        sum = nr;
        ok++;
    }

    /// altfel , verifica daca coloana poate fi alternanta

    for (i=1;i<=k;i++){
        swap(x[i] , y[i]);
    }
    swap(n , m);

    if (check()){
        int nr = 1;
        int aux = 2;
        while (unk){
            if (unk % 2)
                nr = ((long long)nr * aux)%MOD;
            aux = ((long long)aux * aux)%MOD;
            unk/=2;
        }
        sum = (sum + nr)%MOD;
        ok++;
    }
    if (k == 0){
        fprintf (fout,"%d",sum-2);
        return 0;
    }
    /// altfel ai linie inv linie inv SAU imposibil
    if (ok == 2){ /// scade 1 daca pot fi si liniile si col alternante in AC timp
        for (i=1;i<=k;i++){
            swap(x[i] , y[i]);
        }
        swap(n , m);
        sum-=both();
        sum = (sum + MOD)%MOD;
    }
    if (!ok)
        fprintf (fout,"0");
    else fprintf (fout,"%d",sum);
    return 0;
}

Compilation message

plusminus.cpp: In function 'int main()':
plusminus.cpp:89:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d\n",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:95:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d\n",&x[i],&y[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 400 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 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 0 ms 376 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 400 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 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 0 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 0 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 28 ms 2552 KB Output is correct
17 Correct 25 ms 2424 KB Output is correct
18 Correct 25 ms 2428 KB Output is correct
19 Correct 141 ms 2680 KB Output is correct
20 Correct 141 ms 2680 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 400 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 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 0 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 0 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 28 ms 2552 KB Output is correct
17 Correct 25 ms 2424 KB Output is correct
18 Correct 25 ms 2428 KB Output is correct
19 Correct 141 ms 2680 KB Output is correct
20 Correct 141 ms 2680 KB Output is correct
21 Correct 432 ms 11484 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 32 ms 2936 KB Output is correct
24 Correct 32 ms 2936 KB Output is correct
25 Correct 30 ms 2936 KB Output is correct
26 Correct 295 ms 11484 KB Output is correct
27 Correct 316 ms 10488 KB Output is correct
28 Correct 291 ms 12280 KB Output is correct
29 Correct 457 ms 14968 KB Output is correct
30 Correct 583 ms 17784 KB Output is correct