11537 - Secret Problemsetters' Union

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

11537 - Secret Problemsetters' Union

Post by smilitude » Tue Oct 21, 2008 9:37 am

Another important thing to notice is that, at a time there will be at most 5000000 problems in the merged problem bank & at most 100000 problems in any other bank
Does that mean, I will not insert any more problems in the bank if it already has 100000 problems ?
fahim
#include <smile.h>

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11537 - Secret Problemsetters' Union

Post by mmonish » Tue Oct 21, 2008 11:07 am

u wouldn't need to check this condition.

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11537 - Secret Problemsetters' Union

Post by tanmoy » Mon Jul 20, 2009 9:22 pm

i'm getting runtime error for this problem. :(
if you guys kindly check my code and advice me how to solve this problem then it will really great for me.

Code: Select all

#pragma warning (disable : 4786 )
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
#define _pf printf
#define _sc scanf
#define null NULL
#define all(c) (c).begin(),(c).end()

struct cmp{
	bool operator()(const int s1,const int s2){
		return s1>s2;
	}
};

struct PeoSe{
	multiset<int,cmp> S;
	multiset<int,cmp>::iterator it;
}Pr_s[52];

char G[20];
int k;

multiset<int,cmp> s;
multiset<int,cmp>::iterator It;

void Insert(void){
	int R[6];
	int i=0;
	char *p=strtok(G," ");
	p=strtok(null," ");
	while(p){
		int t=atoi(p);
		R[i++]=t;
		p=strtok(null," ");
	}
	int A_0=R[2];
	int X=R[3];
	for(i=1;i<=R[1];i++){
		int v=(A_0+i*X)%100007;
		Pr_s[R[0]].S.insert(v);
		A_0=v;
	}
}


void Remove(void){
	char *p=strtok(G," ");
	p=strtok(null," ");
	int Id=atoi(p);
	p=strtok(null," ");
	int N=atoi(p);
	int C,max=0,min=0;
	for(Pr_s[Id].it=Pr_s[Id].S.begin(),C=1;Pr_s[Id].it != Pr_s[Id].S.end() && C<=N;C++){
		if(C==1) max=(*Pr_s[Id].it);
		if(C==N) min=(*Pr_s[Id].it);
		Pr_s[Id].S.erase(Pr_s[Id].it);
		Pr_s[Id].it=Pr_s[Id].S.begin();
	}
	_pf("%d %d\n",max,min);
}


void Merge(void){
	for(int i=1;i<=k;i++)
		for(Pr_s[i].it=Pr_s[i].S.begin();Pr_s[i].it!=Pr_s[i].S.end();Pr_s[i].it++)
			s.insert(*Pr_s[i].it);
}


void operation(void){
	int R[6];
	int i=0;
	char *p=strtok(G," ");
	p=strtok(null," ");
	while(p){
		int t=atoi(p);
		R[i++]=t;
		p=strtok(null," ");
	}
	int A_0=R[2];
	int X=R[3];
	for(i=1;i<=R[1];i++){
		int v=(A_0+i*X)%100007;
		s.insert(v);
		A_0=v;
	}
}

void solve(void){
	char *p=strtok(G," ");
	p=strtok(null," ");
	int Id=atoi(p);
	p=strtok(null," ");
	int N=atoi(p);
	int C,max=0,min=0;
	for(It=s.begin(),C=1;It != s.end() && C<=N;C++){
		if(C==1) max=(*It);
		if(C==N) min=(*It);
		s.erase(It);
		It=s.begin();
	}
	_pf("%d %d\n",max,min);
}

void clear(void){
	s.clear();
	for(int i=0;i<52;i++)
		Pr_s[i].S.clear();
}

int main(){
	int n;
	gets(G);
	n=atoi(G);
	while(n--){
		gets(G);
		k=atoi(G);
		bool T=true;
		while(1){
			gets(G);
			if(strcmp(G,"Q")==0) break;
			else if(G[0]=='I' && T ) Insert();
			else if(G[0]=='U' && T) Remove();
			else if(G[0]=='M'){
				T=false;
				Merge();
			}
			else if(G[0]=='I' && !T )operation();
			else if(G[0]=='U' && !T)solve(); 
		}
		clear();
	}

	return 0;


}

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11537 - Secret Problemsetters' Union

Post by Articuno » Mon Dec 07, 2009 10:25 am

Can anyone give me some ideas about how to solve this problem......... Someone please reply

dubukuangye
New poster
Posts: 4
Joined: Wed Jul 14, 2010 12:54 pm

Re: 11537 - Secret Problemsetters' Union

Post by dubukuangye » Sat Jul 17, 2010 9:12 am

I also get RE.

#include <iostream>
#include <queue>
using namespace std;
const int MAX = 100;

int B, N, A0, X, K;

int main(){
int case_num, bank_num;;
char order;
cin >> case_num;
for(int i=0; i<case_num; i++){
cin >> bank_num;
priority_queue<int> bank[101];

while( true ){
cin >> order;
if( order=='Q' ){ break; }
if( order=='I' ){
cin >> B >> N >> A0 >> X;
long long A = A0;
for(int cnt=1; cnt<=N; cnt++){
long long tmp = cnt*X;
A += tmp;
A %= 100007;
// A = (A+cnt*X)%100007;
// A = ( A%100007+(cnt%100007)*(X%100007) )%100007;
bank.push(A);
}
}
if( order=='U' ){
cin >> B >> K;
if( K==0 ){ cout << "0 0" << endl; }
else{
cout << bank.top();
bank.pop();
for(int cnt=1; cnt<K-1; cnt++){ bank.pop(); }
cout << " " << bank.top() << endl;
bank.pop();
}
}
if( order=='M' ){
for(int cnt=2; cnt<=bank_num; cnt++){
while( !bank[cnt].empty() ){
int element = bank[cnt].top();
bank[cnt].pop();
bank[1].push( element );
}
}
}
}
}
return 0;
}

Post Reply

Return to “Volume 115 (11500-11599)”