Submission #403734

#	Time	Username	Problem	Language	Result	Execution time	Memory
403734		PedroBigMan	Robots (IOI13_robots)	C++14	90 / 100	245 ms	65540 KiB

robots

#include "robots.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

vector<vector<ll> > ps;

ll Query(ll x1,ll x2, ll y1, ll y2)
{
	ll ans = ps[x2][y2];
	if(y1>0) {ans-=ps[x2][y1-1];}
	if(x1>0) {ans-=ps[x1-1][y2];}
	if(x1>0 && y1>0) {ans+=ps[x1-1][y1-1];}
	return ans;
}

int putaway(int a, int b, int T, int X[], int Y[], int W[], int S[])
{
	vector<ll> A,B; vector<pl> p;
	REP(i,0,a) {A.pb((ll) X[i]);} REP(i,0,b) {B.pb((ll) Y[i]);}
	REP(i,0,T) {p.pb((pl) {(ll) W[i], (ll) S[i]});}
	A.pb(0LL); B.pb(0LL); sort(whole(A)); sort(whole(B));
	vector<vector<ll> > oc; vector<ll> xx; REP(i,0,B.size()) {xx.pb(0);} REP(i,0,A.size()) {oc.pb(xx);}
	ll indA,indB;
	REP(i,0,T)
	{
		indA = (ll) (upper_bound(whole(A),p[i].ff) - A.begin()) -1LL;
		indB = (ll) (upper_bound(whole(B),p[i].ss) - B.begin()) -1LL;
		oc[indA][indB]++;
	}
	REP(i,0,A.size()) {ps.pb(xx);}
	REP(i,0,A.size())
	{
		REP(j,0,B.size())
		{
			if(i==0 && j==0) {ps[i][j]=oc[i][j];}
			else if(i==0) {ps[i][j]=ps[i][j-1]+oc[i][j];}
			else if(j==0) {ps[i][j]=ps[i-1][j]+oc[i][j];}
			else {ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+oc[i][j];}
		}
	}
	if(oc[A.size()-1][B.size()-1]!=0) {return -1;}
	ll ans=0LL;
	ll val; ll sizeA,sizeB;
	REP(i,0,A.size())
	{
		REP(j,0,B.size())
		{
			if(i==A.size()-1 && j==B.size()-1) {continue;}
			sizeA = A.size()-i; sizeB = B.size()-j;
			val = (Query(i,A.size()-1,j,B.size()-1)+sizeA+sizeB-3LL)/(sizeA+sizeB-2LL);
			ans=max(ans,val);
		}
	}
	return ans;
}

Compilation message (stderr)

robots.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
robots.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:91:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    if(i==A.size()-1 && j==B.size()-1) {continue;}
      |       ~^~~~~~~~~~~~
robots.cpp:91:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    if(i==A.size()-1 && j==B.size()-1) {continue;}
      |                        ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10