Submission #619222

#	Time	Username	Problem	Language	Result	Execution time	Memory
619222		Dremix10	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	348 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = "<<x.F<<"-"<<x.S<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
const int N = 1005;
const int MOD = 1e9+7;
const ll INF = 1e18+5;

struct ano{
    int x,y,id;
};

bool cmp(ano a, ano b){
    return min(a.x,a.y) > min(b.x,b.y);
}

bool v[N][N];

void clean(vector<ano> &a){
    while(!a.empty() && v[a.back().x][a.back().y])
        a.pop_back();
}

void print(vector<ano> &arr){
    return;
    for(auto x : arr){
        cerr<<x.x<<" "<<x.y<<" "<<x.id<<endl;
    }
}

long long take_photos(int n, int m, int K, std::vector<int> r, std::vector<int> c) {
    int i,j,k;

    vector<ano> arr(n);
    set<pi> s;

    for(i=0;i<n;i++){
        arr[i] = {r[i],c[i],i};
        s.insert({r[i],c[i]});
    }
    sort(all(arr),cmp);

    //bool v[m][m] = {};
    int p = 0;
    int ans = 0;

    int gaps = max(0,(int)s.size() - k);
    
    

    for(i=0;i<m;i++){
        clean(arr);
        
        if(arr.empty())break;
        if(arr.back().x != i && arr.back().y != i)continue;
        int maxi = 0;
        print(arr);
        do{
            maxi = max(maxi,max(arr.back().x,arr.back().y));
            arr.pop_back();
            clean(arr);
        }while(!arr.empty() && arr.back().x == i || arr.back().y == i);

        for(j=i;j<=maxi;j++)for(k=i;k<=maxi;k++){
            ans += v[j][k] == false;
            v[j][k] = true;
        }
        p2(i,ans)
        p(maxi)
    }
    //assert(arr.empty());
    //assert(ans <= m*m);
    int cnt = 0;

    for(i=0;i<m;i++)
    for(j=0;j<m;j++)
    cnt += v[i][j] == true;

    //assert(cnt == ans);
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:81:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   81 |         }while(!arr.empty() && arr.back().x == i || arr.back().y == i);
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
aliens.cpp:63:9: warning: unused variable 'p' [-Wunused-variable]
   63 |     int p = 0;
      |         ^
aliens.cpp:66:9: warning: unused variable 'gaps' [-Wunused-variable]
   66 |     int gaps = max(0,(int)s.size() - k);
      |         ^~~~

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