Submission #235452

#	Time	Username	Problem	Language	Result	Execution time	Memory
235452		crossing0ver	Robots (IOI13_robots)	C++17	39 / 100	3079 ms	16868 KiB

robots

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#include "robots.h"
using namespace std;
 // X weight  Y size
 int a,b,t,X[50000],Y[50000],W[1000000],S[1000000],mxW,mxS , flag = 1;
 map<int,int> mp;
 ll sufa[50000],sufb[50000];
 ld mxa,mxb;
 vector<int> f,ds;
void count_max() {
	for (int i = 0; i < a; i++) mxW = max (mxW,X[i]);
	for (int i = 0; i < b; i++) mxS = max (mxS,Y[i]);
	for (int i = 0; i < t; i++) 
		if (W[i] >= mxW && S[i] >= mxS) flag = 0;
}
 
int case1() {
	if (a == 0) {
		if (Y[1] > S[1] && Y[0] > S[0]) return 1;
		return 2;
	}
	if (b == 0) {
		if (X[1] > W[1] && X[0] > W[0]) return 1;
		 return 2;
	}
	if ((X[0] > W[0] && Y[0] > S[1] ) || (X[0] > W[1] && Y[0] > S[0]) )
		return 1;
	return 0;
}
 
int case2() {
	set < pair<int,int> > s;
	int cnt = 0;
	for (int i = 0; i < t; i ++) s.insert ({W[i],cnt++});
	set<pair<int,int> > g;
	vector<int> v;
	for (int i = 0; i < a; i++) v.push_back(X[i]);
	int timer = 0;
	while (!s.empty()) {
		timer++;
		for (int j = 0,i; j < v.size() && s.size(); j++) {
			i = v[j];
			auto it  = s.lower_bound({i,0});
			if (it == s.begin()){
				if (j != v.size() - 1)
				swap(v[v.size() - 1],v[j]);
				v.pop_back();
				j--;
			}
			else {
				it--;
				s.erase(it);
			}
		}
	}
	return timer;
}
int bad[100000];
int case3() {
	vector<int> va,vb;
	for (int i = 0; i < a; i++) va.push_back(X[i]);
	for (int i = 0; i < b; i++) vb.push_back(X[i]);
	int timer = 0;
		bool bigflag = 1;
		while(bigflag)  {
			bigflag = 0;
		for (int j = 0; j < a; j++) {
			int i = X[j];
			int in;
			bool flag = 0;
			int maxa = 0, maxb= 0;
			for (int f = 0; f < t; f++) {
				if (!bad[f]) {
					if (W[f] < i) maxa = max(maxa,W[f]),maxb = max(maxb,S[f]),in = f,flag = 1,bigflag = 1;				
				}
			}
			if (!flag) continue;
			bad[in] = 1;
			if (mxa > mxb) {
				for (int i = 0; i < a; i++)
					if (X[i] <= maxa) sufa[i] --;
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= maxb) sufb[i] --;		
			}
			mxa = mxb= 0;
			for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	} 
	}
	for (int j = 0; j < b; j++) {    int maxa = 0, maxb= 0;
			int i = Y[j];
			int in;
			bool flag = 0;
			for (int f = 0; f < t; f++) {
				if (!bad[f]) {
					if (S[f] < i) maxa = max(maxa,W[f]),maxb = max(maxb,S[f]),in = f,flag = 1,bigflag = 1;				
				}
			}
			if (!flag) continue;
			bad[in] = 1;
			if (mxa > mxb) {
				for (int i = 0; i < a; i++)
					if (X[i] <= maxa) sufa[i] --;
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= maxb) sufb[i] --;		
			}  mxa = mxb= 0;
			for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	} 
	}
	if (bigflag) timer++;
	}
	return timer;
}
 
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
	a = A1; b = B1;t = T1;
	for (int i = 0; i < a; i++) X[i] = X1[i],f.push_back(X[i]);
	for (int i = 0; i < b; i++) Y[i] = Y1[i],f.push_back(Y[i]);
	for (int i = 0; i < t; i++) W[i] = W1[i], S[i] = S1[i],f.push_back(W[i]),f.push_back(W[i]);
	sort (X, X + a);
	sort (Y, Y + b);
	for (int i = 0; i < a; i++) {
	if (i)	sufa[i] = sufa[i-1];
		for (int j = 0; j < t; j++)
			if (W[j] < X[i]) sufa[i]++;
	}
	for (int i = 0; i < b; i++) {
	if (i)	sufb[i] = sufb[i-1];
		for (int j = 0; j < t; j++)
			if (S[j] < Y[i]) sufb[i]++;
	}
	for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	}
	sort (f.begin(),f.end());
	int last = INT_MIN;
	int cnt = 0;
	for (int i = 0;i  < f.size(); i++) {
		if (last != f[i]) {
			ds.push_back(f[i]);
			last = f[i];
			mp[f[i]]  = ++cnt;
		}
	}
    count_max();
    if (!flag) return -1;
    if (b == 0)	return case2();
    if (t == 2 && a + b == 2) return case1();
    return case3();
}

Compilation message (stderr)

robots.cpp: In function 'int case2()':
robots.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0,i; j < v.size() && s.size(); j++) {
                     ~~^~~~~~~~~~
robots.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j != v.size() - 1)
         ~~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:136:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (i) sufa[i] = sufa[i-1];
  ^~
robots.cpp:137:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   for (int j = 0; j < t; j++)
   ^~~
robots.cpp:141:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (i) sufb[i] = sufb[i-1];
  ^~
robots.cpp:142:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   for (int j = 0; j < t; j++)
   ^~~
robots.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i  < f.size(); i++) {
                 ~~~^~~~~~~~~~

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