Submission #1025400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025400		vjudge1	Martian DNA (BOI18_dna)	C++17	68 / 100	2062 ms	15196 KiB

dna

#include <bits/stdc++.h>
#define int long long
#define INF LLONG_MAX
#define pii pair<int, int>
using namespace std;

int32_t main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);

     int n, k, r;
     cin >> n >> k >> r;
     vector<vector<int>> pos(k);
     vector<int> dna(n);
     for (int i = 0; i < n; i++)
     {
          cin >> dna[i];
          pos[dna[i]].push_back(i);
     }
     vector<int> maxx(n, 0);
     for (int i = 0; i < r; i++)
     {
          int nucleo, num;
          cin >> nucleo >> num;
          if (pos[nucleo].size() < num)
          {
               cout << "impossible" << endl;
               return 0;
          }
          for (int j = 0; j < n; j++)
          {
               int idx = lower_bound(pos[nucleo].begin(), pos[nucleo].end(), j) - pos[nucleo].begin();
               if (idx + num - 1 < pos[nucleo].size())
                    maxx[j] = max(maxx[j], pos[nucleo][idx + num - 1] - j + 1);
               else
                    maxx[j] = INF;
          }
     }
     cout << *min_element(maxx.begin(), maxx.end()) << endl;

     return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int32_t main()':
dna.cpp:27:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |           if (pos[nucleo].size() < num)
      |               ~~~~~~~~~~~~~~~~~~~^~~~~
dna.cpp:35:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |                if (idx + num - 1 < pos[nucleo].size())
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 0 / 32