Submission #104589

#	Time	Username	Problem	Language	Result	Execution time	Memory
104589		daili	Genetics (BOI18_genetics)	C++14	27 / 100	2079 ms	8324 KiB

genetics

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

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 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26