Submission #1267265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267265		silentloop	Aliens (IOI16_aliens)	C++20	0 / 100	5 ms	8260 KiB

aliens

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;

vector<vector<ll>>vis;

ll tot;

ll calc(ll x, ll y)
{
    ll i, j, cant=0;
    for(i=x; i<=y; i++)
    {
        for(j=x; j<=y; j++)
        {
            if(!vis[i][j])
                cant++;
        }
    }
    return cant;
}

void un(ll x, ll y)
{
    ll i, j;
    for(i=x; i<=y; i++)
    {
        for(j=x; j<=y; j++)
        {
            if(!vis[i][j])
                tot++;
            vis[i][j]=1;
        }
    }
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    ll cant = 0, i, mi, uni, cos, ag;
    vis.resize(m,vector<ll>(m,0));
    vector<pair<ll, ll>> v, nv;
    for (i = 0; i < n; i++)
    {
        if(!vis[r[i]][c[i]])
        {
            v.pb({r[i], c[i]});
            tot++;
            cant++;
        }
        vis[r[i]][c[i]]=1;
    }
    sort(all(v));
    while (cant > k)
    {
        mi = LLONG_MAX;
        uni = 0;
        for (i = 0; i < sz(v)-1; i++)
        {
            cos = calc(v[i].fr, v[i+1].fr);
            if (mi > cos)
            {
                mi = cos;
                uni = i;
            }
        }
        un(v[uni].fr,v[uni+1].fr);
        cant--;
        nv.resize(0);
        for(i=0; i<sz(v); i++)
        {
            if(uni==i)
            {
                nv.pb({v[i].fr,v[i+1].se});
                i++;
            }
            else
                nv.pb(v[i]);
        }
        swap(nv,v);
    }
    return tot;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40