Submission #139873

#	Time	Username	Problem	Language	Result	Execution time	Memory
139873		SirCeness	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	380 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000000000009
#define mod 1000000007
#define ppair(x) "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

vector<pair<int, int> > arr;

ll sq(int a, int b){
	if (a < b) return 0;
	return (ll)(a-b+1)*(ll)(a-b+1);
}

ll getcost(int a, int b){
	return sq(arr[b].x, arr[a].y) - sq(arr[a].x, arr[a].y) - sq(arr[b].x, arr[b].y) + sq(arr[a].x, arr[b].y);
}

int cmp(const pair<int, int>& lhs, const pair<int, int>& rhs){
	if (lhs.second == rhs.second) return lhs.first > rhs.first;
	return lhs.second < rhs.second;
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	vector<pair<int, int> > ekle1;
	for (int i = 0; i < n; i++) if (r[i] >= c[i]) ekle1.pb(mp(r[i], c[i]));
	else ekle1.pb(mp(c[i], r[i]));
	
	sort(ekle1.begin(), ekle1.end(), cmp);
	arr.pb(ekle1[0]);
	//cout << ppair(ekle1[0]) << " ";
	for (int i = 1; i < n; i++){
		//cout << ppair(ekle1[i]) << " ";
		if (ekle1[i].second == arr.back().second) continue;
		if (ekle1[i].first <= arr.back().first) continue;
		arr.pb(ekle1[i]);
	}
	//cout << endl;
	
	//for (int i = 0; i < arr.size(); i++) cout << ppair(arr[i]) << endl;
	
	ll ans = 0;
	for (int i = 0; i < arr.size(); i++){
		ans += sq(arr[i].x, arr[i].y);
		if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
	}
	
	set<pair<ll, int> > st;
	for (int i = 0; i < arr.size()-1; i++){
		ll cost = getcost(i, i+1);
		st.insert(mp(cost, i));
	}
	
	vector<int> bef(arr.size());
	for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
	bef[0] = -1;
	vector<int> nex(arr.size());
	for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
	nex[arr.size()-1] = -1;
	
	
	for (int q = 0; q < (int)arr.size()-k; q++){
		//for (pair<ll, int> eleman: st) cout << ppair(eleman) << " "; cout << endl;
		int i = st.begin() -> second;
		ans += st.begin() -> first;
		int b = bef[i];
		int nx = nex[nex[i]];
		st.erase(st.begin());
		if (b != -1){
			ll costb = getcost(b, i);
			int tmp = st.size();
			st.erase(st.find(mp(costb, b)));
			if (tmp-1 != st.size()) assert(0);
		}
		if (nx != -1){
			ll costn = getcost(nex[i], nx);
			int tmp = st.size();
			st.erase(st.find(mp(costn, nex[i])));
			if (tmp-1 != st.size()) assert(0);
		}
		
		arr[i].x = arr[nex[i]].x;
		
		nex[i] = nx;
		if (nx != -1) bef[nx] = i;
		
		if (b != -1) st.insert(mp(getcost(b, i), b));
		if (nx != -1) st.insert(mp(getcost(i, nx), i));
		
	}
	
	
	
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++){
                  ~~^~~~~~~~~~~~
aliens.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
       ~~~~^~~~~~~~~~~~~
aliens.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++){
                  ~~^~~~~~~~~~~~~~
aliens.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
                  ~~^~~~~~~~~~~~
aliens.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
                  ~~^~~~~~~~~~~~~~
aliens.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~
aliens.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (tmp-1 != st.size()) assert(0);
        ~~~~~~^~~~~~~~~~~~

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