제출 #309897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309897		CaroLinda	비스킷 담기 (IOI20_biscuits)	C++14	9 / 100	1171 ms	1040264 KiB

biscuits

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

#define debug printf
#define ff first
#define ss second
#define sz(x) (int)(x.size()) 
#define all(x) x.begin(),x.end()
#define ll long long
 
using namespace std ;
 
 
long long count_tastiness(long long x, vector<long long> a ) 
{
 
 
	while( (int)(a.size()) < 60 ) { a.push_back(0LL) ; } ;
 
	vector<ll> pos(1,0LL) ;
 
	ll curSoma = 0LL ;
 
	vector<pair<ll,int>> vec ;

	for(int i = 0 ; i < 60 && (LLONG_MAX/x) > (1LL<<i); i++ )
	{
		curSoma += a[i] * (1LL<<i) ;
 		vec.push_back( make_pair( curSoma - x*(1LL<<i) , i )  ) ;
 
	}

	sort(all(vec)) ;
	vector<int> meuIdx(60, -1) ; //eu vou atualizar quando encontrar 
	//alguem que eh maior que ele


	int ptr = 0 ;
	while( ptr < sz(vec) && vec[ptr].first < 0LL )
	{
		meuIdx[ vec[ptr].second ] = 0 ;
		ptr++ ;
	}

	for(int i = 0 ; i < (int)(vec.size()) ; i++ )
	{

		int getIdx = meuIdx[i] ;
		if(getIdx == -1) getIdx = sz(pos) ;

		for(int j = 0 ; j < getIdx ; j++ )
		{
			pos.push_back( pos[j] + x*(1LL<<i) ) ;
			while(ptr < sz(vec) && pos.back() > vec[ptr].first )
			{
				if( vec[ptr].second > i ) 
					meuIdx[ vec[ptr].second ] = sz(pos)-1 ;
				ptr++ ;
			}
		}

	}
 
	return (int)(pos.size() ) ;
 
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23