Submission #425719

#	Time	Username	Problem	Language	Result	Execution time	Memory
425719		ngrace	Aliens (IOI16_aliens)	C++14	0 / 100	18 ms	460 KiB

aliens

#include "aliens.h"
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <set>
#include <limits.h>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second

long long area(int r, int l){
    return (r-l+1)*(r-l+1);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    if(k==1){
        long long low=LLONG_MAX;
        long long high=0;
        for(int i=0;i<n;i++){
            if(r[i]<low) low=r[i];
            if(r[i]>high) high=r[i];
            if(c[i]<low) low=c[i];
            if(r[i]>high) high=c[i];
        }
        return area(high,low);
    }
    else if(k==n && m<=100){//sub 1
        v<v<bool>> squares(m,v<bool>(m,false));
        for(int i=0;i<n;i++){
            int low=min(r[i],c[i]);
            int high=max(r[i],c[i]);
            for(int a=low;a<=high;a++){
                for(int b=low;b<=high;b++){
                    squares[a][b]=true;
                }
            }
        }

        long long out=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                out+=squares[i][j];
            }
        }
        return out;
    }
    else{//assume sub 2
        //as all along diagonal can do dp with n^3
        set<pii> pos;
        for(int i=0;i<n;i++) pos.insert({min(r[i],c[i]), max(r[i],c[i])});

        while(pos.size()>k){
            long long extra=LLONG_MAX;
            pii one;
            pii two;
            for(pii it:pos){
                for(pii pt:pos){
                    if(it!=pt){
                        if(pt.fi>=it.fi){
                            if(pt.fi<=it.se && pt.se<=it.se){
                                one=it;
                                two=pt;
                                extra=0;
                                break;
                            }
                            else if(pt.fi<=it.se){
                                long long cur=area(pt.se,it.fi);
                                cur-= area(it.se,it.fi);
                                cur-= area(pt.se,pt.fi);
                                cur+= area(it.se,pt.fi);
                                if(cur<extra){
                                    extra=cur;
                                    one=it;
                                    two=pt;
                                }
                            }
                            else{
                                long long cur=area(pt.se,it.fi);
                                cur-= area(it.se,it.fi);
                                cur-= area(pt.se,pt.fi);
                                if(cur<extra){
                                    extra=cur;
                                    one=it;
                                    two=pt;
                                }
                            }
                        }
                    }
                    if(extra==0) break;
                }
                if(extra==0) break;
            }
            pii newSquare={min(one.fi,two.fi),max(one.se,two.se)};
            pos.erase(one);
            pos.erase(two);
            pos.insert(newSquare);
        }

        v<v<bool>> squares(m,v<bool>(m,false));
        for(pii it:pos){
            int low=it.fi;
            int high=it.se;
            for(int a=low;a<=high;a++){
                for(int b=low;b<=high;b++){
                    squares[a][b]=true;
                }
            }
        }

        long long out=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                out+=squares[i][j];
            }
        }
        return out;
    }
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:55:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while(pos.size()>k){
      |               ~~~~~~~~~~^~

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