Submission #890990

#	Time	Username	Problem	Language	Result	Execution time	Memory
890990		AccountName	Martian DNA (BOI18_dna)	C++14	0 / 100	20 ms	3164 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
#define int long long

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int dna_len, alphabet_size, req_nucleobase_no;
    cin >> dna_len >> alphabet_size >> req_nucleobase_no;
    
    int dna[dna_len];
    for(int i = 0; i < dna_len; i++)
    {
		cin >> dna[i];
	}
	int req_nucleobase[alphabet_size];
    int extra_nucleobases[alphabet_size];
    for(int i = 0; i < alphabet_size; i++)
    {
		req_nucleobase[i] = -1;
		extra_nucleobases[i] = 0;
	}
    for(int i = 0; i < req_nucleobase_no; i++)
    {
		int nucleobase;
		cin >> nucleobase;
		cin >> req_nucleobase[nucleobase];
	}
    
    int no_of_req_met, shortest_len = 0;
    int left = 0;
    for(int right = 0; right < dna_len; right++)
    {
		if(req_nucleobase[dna[right]] > 0)
		{
			req_nucleobase[dna[right]]--;
			if(req_nucleobase[dna[right]] == 0)
			{
				no_of_req_met++;
			}
		}
		else
		{
			extra_nucleobases[dna[right]]++;
		}
		
		bool can_delete = (req_nucleobase[dna[left]] == -1 or extra_nucleobases[dna[left]] > 0);
		while(can_delete and left < right)
		{
			//cout << left << " " << dna[left] << " ";
			//cout << req_nucleobase[dna[left]] << " " << extra_nucleobases[dna[left]] << "\n";
			left++;
			extra_nucleobases[dna[left]]--;
			can_delete = (req_nucleobase[dna[left]] == -1 or extra_nucleobases[dna[left]] > 0);
		}
		
		if(no_of_req_met == req_nucleobase_no)
		{
			int curr_len = right - left + 1;
			shortest_len = (shortest_len == 0)? curr_len : min(curr_len, shortest_len);
		}
		//cout << left << " test " << right << "\n";
	}
	
    if(no_of_req_met != req_nucleobase_no)
    {
		cout << "impossible";
	}
	else
	{
		cout << shortest_len;
	}
    
	return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:67:5: warning: 'no_of_req_met' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     if(no_of_req_met != req_nucleobase_no)
      |     ^~

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