Submission #483289

#	Time	Username	Problem	Language	Result	Execution time	Memory
483289		MohamedAliSaidane	Martian DNA (BOI18_dna)	C++14	100 / 100	61 ms	4060 KiB

dna

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (int)(1e8)
#define INF (ll) (1e18)
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ld pointdist(ld x, ld y, ld point) { return ((x-point)*(y-point))/abs(x-y); }
ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //East, West, South, North
const int xcav[8] = {1,2,2,1,-1,-2,-2,-1};
const int ycav[8] = {-2,-1,1,2,2,1,-1,-2};
const int crapx[4] = {0,2,0,-2};
const int crapy[4] = {-2,0,2,0};
////////////******SOLUTION******\\\\\\\\\\\

const int MAX_N = 2e5 + 4;
int n, k, r;
vector<int> dna;
int m[MAX_N];

bool f(int x)
{
    int seen[k];
    memset(seen,0,sizeof(seen));
    int cnt = 0;
    for(int i = 0; i <x; i ++)
    {
        seen[dna[i]] ++;
        if(seen[dna[i]] == m[dna[i]])
            cnt ++;
    }
    if(cnt == r)
        return true;
    for(int i = x; i <n; i ++)
    {
        if(m[dna[i-x]] != -1)
        {
            seen[dna[i-x]] --;
            if(seen[dna[i-x]] == m[dna[i-x]] - 1)
                cnt --;
        }
        if(m[dna[i]] != -1)
        {
            seen[dna[i]] ++;
            if(seen[dna[i]] == m[dna[i]])
                cnt ++;
        }
        if(cnt == r)
            return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k >> r;
    memset(m,-1,sizeof(m));
    for(int i = 0; i <n; i ++ )
    {
        int a; cin >> a;
        dna.pb(a);
    }
    for(int i = 0; i < r; i ++)
    {
        int a, b;
        cin >> a >> b;
        m[a] = b;
    }
    int ans = -1;
    int debut = 1;
    int fin = n;
    while(debut <= fin)
    {
        int mid = (debut + fin)/2;
        if(f(mid))
        {
            ans = mid;
            fin = mid - 1;
        }
        else
            debut = mid + 1;
    }
    if(ans == -1)
        cout << "impossible\n";
    else
        cout << ans << '\n';
}
/* Case that bugs my program:
5280
11
54 19 70 69 33 27 91 77 30 47 6
*/
/*
Identify problem diagram: Brute force, Greedy, Dynamic Programming, Divide and Conquer
Reformulate the problem into something more theoretical
Search for multiple approaches: select the seemingly optimal one
Remember that you're the king of CP
Change your approach
Imagine Corner cases before submitting
Don't spend too much time on the problem: move on !
*/

Compilation message (stderr)

dna.cpp:28:1: warning: multi-line comment [-Wcomment]
   28 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

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