oj.uz

Submission #104589

# Submission time Handle Problem Language Result Execution time Memory
104589 2019-04-08T09:52:26 Z daili Genetics (BOI18_genetics) C++14
27 / 100
 2000 ms 8324 KB 
#include <bits/stdc++.h>

using namespace std;

int diff(string a, string b)
{
    int cnt = 0;
    for (int i = 0; i < a.size() ; i++)
    {
        if (a[i] != b[i])
        {
            cnt++;
        }
    }
    return cnt;
}

void Task1(int n, int m ,int k)
{
    vector<string> all;
    for (int i =0; i <n ; i++)
    {
        string x;
        cin >> x;

        all.push_back(x);
    }

    for (int i = 0; i < n; i++)
    {
        bool flag = true;
        for (int j = 0; j < n; j++)
        {
            if (i == j)
            {
                continue;
            }

            if (diff(all[i], all[j]) != k)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            cout << i+1 << "\n";
            return;
        }
    }
}

void TaskB(int n, const int m, int k)
{
    vector<bitset<4101> > all;
    for (int i = 0; i < n; i++)
    {
        bitset<4101> bit;
        string x;
        cin >> x;

        for (int j = 0; j < m; j++)
        {
            if (x[j] == 'A')
            {
                bit[j] = 1;
            }
        }
        all.push_back(bit);
    }

    for (int i = 0; i < n; i++)
    {
        bool flag = true;
        for (int j = 0; j < n; j++)
        {
            if (i == j)
            {
                continue;
            }

            bitset<4101> xr = all[i] ^ all[j];
            if (xr.count() != k)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            cout << i+1 << "\n";
            return;
        }
    }

}

void Solve(int n, int m, int k)
{
  vector<string> all;
  vector<pair<string,int>> possible;

  for (int i =0; i < n; i++)
  {
      string x;
      cin >> x;
      all.push_back(x);
      possible.push_back({x, i+1});
  }

  while(true)
  {
      vector<pair<string,int>> possible2;
      string x = possible[0].first;

      for (int i = 1; i < possible.size(); i++)
      {
          if (diff(x, possible[i].first) == k)
          {
              possible2.push_back(possible[i]);
          }
      }

      if (possible2.size() == possible.size()-1)
      {
          bool flag = true;
          for (int i =0; i <n; i++)
          {
              if (i == possible[0].second-1)
              {
                  continue;
              }


              if (diff(all[i], x) != k)
              {
                  flag = false;
                  break;
              }
          }
          if (flag)
          {
              cout << possible[0].second << "\n";
              return;
          }
      }
      possible = possible2;
  }
}



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;

    /*if (n <= 100 && m <= 100)
    {
        Task1(n, m, k);
    }
    else
    {
        TaskB(n, m, k);
    }*/

    Solve(n, m, k);
}

Compilation message

genetics.cpp: In function 'int diff(std::__cxx11::string, std::__cxx11::string)':
genetics.cpp:8:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size() ; i++)
                     ~~^~~~~~~~~~
genetics.cpp: In function 'void TaskB(int, int, int)':
genetics.cpp:83:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (xr.count() != k)
                 ~~~~~~~~~~~^~~~
genetics.cpp: In function 'void Solve(int, int, int)':
genetics.cpp:116:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 1; i < possible.size(); i++)
                       ~~^~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Execution timed out 2079 ms 8324 KB Time limit exceeded
19 Halted 0 ms 0 KB -