Submission #182405

#	Time	Username	Problem	Language	Result	Execution time	Memory
182405		Ruxandra985	Plus Minus (BOI17_plusminus)	C++14	100 / 100	583 ms	17784 KiB

plusminus

#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 (stderr)

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 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46