oj.uz

Submission #890990

# Submission time Handle Problem Language Result Execution time Memory
890990 2023-12-22T05:53:55 Z AccountName Martian DNA (BOI18_dna) C++14
0 / 100
 20 ms 3164 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -