oj.uz

Submission #5747

# Submission time Handle Problem Language Result Execution time Memory
5747 2014-05-15T13:16:46 Z model_code 선다형 시험 (TOKI14_multiple) C++
100 / 100
 24 ms 48620 KB 
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <deque>
#include <queue>
#include <algorithm>
#include <functional>
#include <utility>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstdlib>

//#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

#define foreach(it, x) for (typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define LL long long

#define MODULO 1000000007L
#define MAX_N 2001
#define MAX_OPTIONS 5

using namespace std;

int N, rightA, rightB;

int nSame, nDiff;
char answerA[MAX_N];
char answerB[MAX_N];
bool same[MAX_N];
int sameCount[MAX_N];
int diffCount[MAX_N];
int TSAME[MAX_N][MAX_N]; // 16 MB
int TDIFF[MAX_N][MAX_N]; // 16 MB
int COMB[MAX_N][MAX_N];  // 16 MB

void readInput()
{
    cin >> N >> rightA >> rightB;
    for (int i = 0; i < N; i++)
    {
        cin >> answerA[i];
    }
    for (int i = 0; i < N; i++)
    {
        cin >> answerB[i];
    }
    
    // Determine sameness
    nSame = 0;
    nDiff = 0;
    for (int i = 0; i < N; i++)
    {
        same[i] = (answerA[i] == answerB[i]);
    }
    
    string s;
    for (int i = 0; i < N; i++)
    {
        int count = 0;
        
        cin >> s;
        for (int j = 0; j < MAX_OPTIONS; j++)
        {
            if (s[j] != '.')
            {
                count++;
            }
        }

        if (same[i])
        {
            sameCount[nSame++] = count;
        }
        else
        {
            diffCount[nDiff++] = count;
        }
    }
    
    // DEBUG
    /*cout << "---------- QUESTION PROFILE ----------" << endl;
    cout << "nSame = " << nSame << "  nDiff = " << nDiff << endl;
    cout << "sameCounts:";
    for (int i = 0; i < nSame; i++)
    {
        cout << " " << sameCount[i];
    }
    cout << endl;
    cout << "diffCounts:";
    for (int i = 0; i < nDiff; i++)
    {
        cout << " " << diffCount[i];
    }
    cout << endl;*/
}

void calcSame()
{
    TSAME[0][0] = 1;
    TSAME[0][1] = sameCount[0] - 1;
    for (int b = 2; b <= nSame; b++)
    {
        TSAME[0][b] = 0;
    }
    
    for (int n = 1; n <= nSame; n++)
    {
        TSAME[n][0] = TSAME[n - 1][0];
        
        for (int b = 1; b <= nSame; b++)
        {
            TSAME[n][b] = ((LL)TSAME[n - 1][b] + (LL)TSAME[n - 1][b - 1] * (LL)(sameCount[n] - 1))
                          % MODULO;
        }
    }
    
    // DEBUG
    /*cout << "--------- TSAME -----------" << endl;
    for (int n = 0; n < nSame; n++)
    {
        cout << "n = " << setw(3) << n << "  :";
        for (int b = 0; b <= nSame; b++)
        {
            cout << setw(4) << TSAME[n][b];
        }
        cout << endl;
    }*/
}

void calcDiff()
{
    TDIFF[0][0] = 1;
    TDIFF[0][1] = diffCount[0] - 2;
    for (int e = 2; e <= nDiff; e++)
    {
        TDIFF[0][e] = 0;
    }
    
    for (int n = 1; n <= nDiff; n++)
    {
        TDIFF[n][0] = TDIFF[n - 1][0];
        
        for (int e = 1; e <= nDiff; e++)
        {
            TDIFF[n][e] = ((LL)TDIFF[n - 1][e] + (LL)TDIFF[n - 1][e - 1] * (LL)(diffCount[n] - 2))
                          % MODULO;
        }
    }

    // DEBUG
    /*cout << "--------- TDIFF -----------" << endl;
    for (int n = 0; n < nDiff; n++)
    {
        cout << "n = " << setw(3) << n << "  :";
        for (int e = 0; e <= nDiff; e++)
        {
            cout << setw(4) << TDIFF[n][e];
        }
        cout << endl;
    }*/
}

void calcComb()
{
    COMB[0][0] = 1;
    
    for (int i = 1; i <= N; i++)
    {
        COMB[i][0] = 1;
        for (int j = 1; j < i; j++)
        {
            COMB[i][j] = ((LL)COMB[i - 1][j - 1] + (LL)COMB[i - 1][j])
                         % MODULO;
        }
        COMB[i][i] = 1;
    }

    // DEBUG
    /*cout << "--------- COMB -----------" << endl;
    for (int i = 0; i < N; i++)
    {
        cout << "i = " << setw(3) << i << "  :";
        for (int j = 0; j <= i; j++)
        {
            cout << setw(4) << COMB[i][j];
        }
        cout << endl;
    }*/
}

LL fSame(int a, int b){
    if ((a < 0) || (b < 0)) return 1;
    return TSAME[a][b];
}

LL fDiff(int a, int b){
    if ((a < 0) || (b < 0)) return 1;
    return TDIFF[a][b];
}

void writeOutput()
{
    int a, b, c, d, e;
    // a: #same, both correct
    // b: #same, both wrong
    // c: #diff, A correct
    // d: #diff, B correct
    // e: #diff, both wrong
    
    int answer = 0;
    int wrongA = N - rightA;
    int wrongB = N - rightB;
    
    for (int e = 0; e <= nDiff; e++)
    {
        //cout << "try e = " << e << endl;
        int partialD = nDiff + wrongA - wrongB - e;
        //cout << "try d = " << (double)partialD * 0.5 << endl;
        if (partialD >= 0 && (partialD % 2) == 0)
        {
            d = partialD / 2;
            c = nDiff - d - e;
            //cout << "try c = " << c << endl;
            if (c >= 0)
            {
                b = wrongA - d - e;
                //cout << "try b = " << b << endl;
                if (b >= 0)
                {
                    a = nSame - b;
                    //cout << "try a = " << a << endl;
                    if (a >= 0)
                    {
                        /*cout << "a = " << a <<
                              "  b = " << b <<
                              "  c = " << c <<
                              "  d = " << d <<
                              "  e = " << e << endl;*/
                        //cout << TSAME[nSame - 1][b] << " " << TDIFF[nDiff - 1][e] << " " << COMB[c + d][c] << endl;
                        int addition =  (LL)((fSame(nSame - 1, b) *
                                              fDiff(nDiff - 1, e) % MODULO) *
                                        (LL)COMB[c + d][c]) % MODULO;
//                        cout << nSame << " " << nDiff << endl;
//                       cout << a << " " << b << " " << c << " " << d << " " << e << endl;
//                        cout << "+" << c+d << " " << c <<  "::" << TSAME[nSame - 1][b] << " " << TDIFF[nDiff - 1][e] << endl;
//                        cout << "addition = " << addition << endl;
                    
                        // Update answer
                        answer = ((LL)answer + (LL)addition) % MODULO;
                    }
                }
            }
        }
    }
    
    cout << answer << endl;
}

int main()
{
    readInput();
    calcSame();
    calcDiff();
    calcComb();
    writeOutput();

    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48620 KB Output is correct
2 Correct 0 ms 48620 KB Output is correct
3 Correct 0 ms 48620 KB Output is correct
4 Correct 0 ms 48620 KB Output is correct
5 Correct 0 ms 48620 KB Output is correct
6 Correct 0 ms 48620 KB Output is correct
7 Correct 0 ms 48620 KB Output is correct
8 Correct 0 ms 48620 KB Output is correct
9 Correct 0 ms 48620 KB Output is correct
10 Correct 0 ms 48620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48620 KB Output is correct
2 Correct 0 ms 48620 KB Output is correct
3 Correct 0 ms 48620 KB Output is correct
4 Correct 24 ms 48620 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48620 KB Output is correct
2 Correct 4 ms 48620 KB Output is correct
3 Correct 0 ms 48620 KB Output is correct
4 Correct 8 ms 48620 KB Output is correct
5 Correct 8 ms 48620 KB Output is correct
6 Correct 8 ms 48620 KB Output is correct
7 Correct 12 ms 48620 KB Output is correct
8 Correct 12 ms 48620 KB Output is correct
9 Correct 12 ms 48620 KB Output is correct
10 Correct 20 ms 48620 KB Output is correct