oj.uz

Submission #104599

# Submission time Handle Problem Language Result Execution time Memory
104599 2019-04-08T10:07:57 Z daili Genetics (BOI18_genetics) C++14
0 / 100
 2000 ms 8640 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)
      {
          possible2.push_back(possible[0]);
      }
      possible = possible2;
      if (possible.size() == 1)
      {
        cout << possible.back().second  << "\n";
        return;
      }
      if (possible.size() == 2)
      {
        for (int i = 0; i < 2; i++)
            {
                bool flag = true;
                for (int j = 0; j < n; j++)
                {
                    if (possible[i].second-1 == j)
                    {
                        continue;
                    }

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



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
0 / 27.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 8640 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 2082 ms 8640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

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