Submission #235468

#	Time	Username	Problem	Language	Result	Execution time	Memory
235468		crossing0ver	Robots (IOI13_robots)	C++17	28 / 100	763 ms	36944 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[50001],Y[50001],W[1000001],S[1000001],mxW,mxS , flag = 1,kt[1000000][2];
 map<int,int> mp;
 ll sufa[50001],sufb[50001];
 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] --;
				for (int i = 0;i < t; i++) if (!bad[i] && maxa == W[i]) {bad[i] = 1;break;}
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= maxb) sufb[i] --;
				for (int i = 0;i < t; i++) if (!bad[i] && maxb == S[i]) {bad[i] = 1;break;}		
			}
			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;
			if (mxa > mxb) {
				for (int i = 0; i < a; i++)
					if (X[i] <= maxa) sufa[i] --;
				for (int i = 0;i < t; i++) if (!bad[i] && maxa == W[i]) {bad[i] = 1;break;}
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= maxb) sufb[i] --;
					for (int i = 0;i < t; i++) if (!bad[i] && maxb == S[i]) {bad[i] = 1;break;}		
			}  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);
	int last = INT_MIN;
	int cnt = 0;
    count_max();
    if (!flag) return -1;
    if (b == 0)	return case2();
    	for (int i = a-1; i >= 0; i--) {
	if (i)	sufa[i] = sufa[i+1];
		for (int j = 0; j < t; j++)
			if (W[j] >= X[i] && !kt[j][0]) sufa[i]++,kt[j][0] = 0;
	}
	for (int i = b - 1; i >= 0; i--) {
	if (i)	sufb[i] = sufb[i+1];
		for (int j = 0; j < t; j++)
			if (S[j] >= Y[i] && !kt[j][0]) sufb[i]++,kt[j][1] = 1;
	}
	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 (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 case3()':
robots.cpp:115:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < b; i++)
     ^~~
robots.cpp:117:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
      for (int i = 0;i < t; i++) if (!bad[i] && maxb == S[i]) {bad[i] = 1;break;}  
      ^~~
robots.cpp:101:8: warning: variable 'in' set but not used [-Wunused-but-set-variable]
    int in;
        ^~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:144:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (i) sufa[i] = sufa[i+1];
  ^~
robots.cpp:145: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:149:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (i) sufb[i] = sufb[i+1];
  ^~
robots.cpp:150: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:138:6: warning: unused variable 'last' [-Wunused-variable]
  int last = INT_MIN;
      ^~~~
robots.cpp:139:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

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