Submission #138710

#	Time	Username	Problem	Language	Result	Execution time	Memory
138710		almogwald	The Big Prize (IOI17_prize)	C++14	97.41 / 100	58 ms	508 KiB

prize

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>

#include "prize.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define maxl 10000000000
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<int,int> point;
lol sum=0;
veci merge(veci a ,veci b){
	int i=0,j=0;
	veci ans;
	while(i<a.size()&&j<b.size()){
		if(a[i]<b[j]){
			ans.push_back(a[i++]);
			sum+=j;
		}else{
			ans.push_back(b[j++]);
		}
	}
	while(i<a.size()){
		ans.push_back(a[i++]);
		sum+=j;
	}
	while(j<b.size()){
		ans.push_back(b[j++]);
	}
	return ans;
}
veci mergesort(veci a){
	if(a.size()==1){
		return a;
	}
	veci b,c;
	fori(i,a.size()){
		if(i<a.size()/2){
			b.push_back(a[i]);
		}else{
			c.push_back(a[i]);
		}
	}
	b=mergesort(b);
	c=mergesort(c);
	return merge(b,c);
}
int find_best(int n) {
	if(n<5000){
		for(int i = 0; i < n; i++) {
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	int m=0;
	int s=0;int ss=0;
	fori(i,500){
		vector<int> res = ask(i);
		if(res[0] + res[1]>m){
			m=res[0] + res[1];
			ss+=s;
			s=0;
		}
		if(res[0] + res[1]==m){
			s++;
		}else{
			ss++;
		}
		if(res[0] + res[1] == 0)
			return i;
	}
	vector<pair<point,point>> tos;
	tos.push_back({{500,n-1},{ss,0}});
	while(true){
		pair<point,point> cur=tos.back();
		tos.pop_back();
		int l=cur.first.first;
		int r=cur.first.second;
		int ll=cur.second.first;
		int rr=cur.second.second;
		if(ll+rr==m){
			continue;
		}
		int m1=(l+r)/2;
		int m2=m1;
		int f=0;
		while(m2<=r){
			vector<int> res = ask(m2++);
			if(res[0] + res[1] == 0)
				return m2-1;
			if(res[0] + res[1] == m){
				tos.push_back({{l,m1-1},{ll,res[1]+f}});
				tos.push_back({{m2,r},{res[0],rr}});
				m2--;
				break;
			}
			f++;
		}
		if(m2>r){
			tos.push_back({{l,m1-1},{ll,rr+f}});
		}
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'veci merge(veci, veci)':
prize.cpp:20:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
prize.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
prize.cpp:28:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()){
        ~^~~~~~~~~
prize.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<b.size()){
        ~^~~~~~~~~
prize.cpp: In function 'veci mergesort(veci)':
prize.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
prize.cpp:42:7:
  fori(i,a.size()){
       ~~~~~~~~~~                
prize.cpp:42:2: note: in expansion of macro 'fori'
  fori(i,a.size()){
  ^~~~
prize.cpp:43:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<a.size()/2){
      ~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 77.41 / 80