OJ Board

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int troba (vector <long long> res, long long n){
    for (int i=0; i<res.size(); i++) if (res[i]==n) return i;
    return -44;
}

int main(){
    vector <pair <long long, long long> > nums;
    pair <long long, long long> aux;
    vector <long long> res;
    while (cin>>aux.first>>aux.second){
          nums.push_back (aux);
          res.push_back (aux.second);
    }
    sort (nums.begin(), nums.end());
    vector <long long> v (nums.size(), 0);
    vector <vector <long long> > seq (nums.size());
    long long respos=0, resmax=0;
    for (int i=0; i<nums.size(); i++){
        long long pos=i, maxi=0;
        for (int j=0; j<i; j++){
            if (nums[j].second>nums[i].second and nums[j].first<nums[i].first) if (v[j]>maxi){maxi=v[j]; pos=j;}
        }
        seq[i]=seq[pos];
        seq[i].push_back (i);
        v[i]=max(maxi, v[i]);
        v[i]++;
        if (v[i]>resmax) {respos=i; resmax=v[i];}
    }
    cout<<resmax<<endl;
    for (int i=0; i<seq[respos].size(); i++){
        long long a=troba (res, nums[seq[respos][i]].second);
        cout<<a+1<<":= "<<nums[seq[respos][i]].first<<" "<<nums[seq[respos][i]].second<<endl;
    }
    system ("pause");
}

Code: Select all

delete after helloneo's Reply
thx helloneo!

Code: Select all

#include<iostream>
#include<cstdlib>
using namespace std;
int n;
struct par{
	int first;
	int second;
	int eskiyer;
};
par dizi[100000];
int cmp(const void* a, const void *b){return ((*( par * )a).first - (*( par *)b).first);}
int best[100001],parent[100001];
int main()
{
	int end=0;
	while(1)
	{
		if(cin.eof()){end--;break;}
			cin>>dizi[end].first>>dizi[end].second;
			dizi[end].eskiyer=end;
			end++;
	}
	for(int i=0;i<end;i++){best[i]=1;parent[i]=i;}
	qsort(dizi,end,sizeof(par),cmp);
	/*
	for(int i=0;i<end;i++)
		cout<<dizi[i].first<<' '<<dizi[i].second<<endl;
		*/
	for(int i=1;i<end;i++)
		for(int j=0;j<i;j++)
			if(dizi[i].first>dizi[j].first&&

					dizi[i].second<dizi[j].second&&

						best[i]<best[j]+1){

				best[i]=best[j]+1;
				parent[i]=j;

			}
	int max=0;
	int old=0,ydk=0;
	for(int i=0;i<end;i++)if(max<best[i]){max=best[i];ydk=i;}
	cout<<max<<endl;
	while(ydk!=old)
	{
		old=ydk;
		cout<<dizi[ydk].eskiyer+1<<endl;
		ydk=parent[ydk];
	}
	return 0;
}

Code: Select all

/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iterator>

using namespace std;

vector<pair<int,pair<int,int> > > elephants;

bool check (const pair<int,pair<int,int> > & left, const pair<int,pair<int,int> >& right) { //mem function
    return (left.second.first<right.second.first)&&(left.second.second>right.second.second);
}

bool sort_pred (const pair<int,pair<int,int> > & left, const pair<int,pair<int,int> > & right){
    if (left.second.first==right.second.first){
        return left.second.second<right.second.second; //Switch inequality value?
    }
    return left.second.first>right.second.first;
}

vector<int> answers;
int p [1001];
int m [1001] = {0};

void print_recurse (int i, int p_i){
    answers.push_back(elephants[i].first);
    if(p_i==-1){
        //cerr<<answers.size()<<endl;
        for(int i = 0;i<answers.size();i++){
            cout<<answers[i]<<endl;
        }
        return;
    }
    //cerr<<elephants[i].first<<" <<"<<endl;

    print_recurse(p_i,p[p_i]);

}

int main (){
    //freopen("isbiggersmarter.txt", "r", stdin);
    int w, iq;
    int c = 1;
    string garbage;
    while (getline(cin,garbage)){
        stringstream ss;
        ss<<garbage;
        ss>>w>>iq;
        elephants.push_back(make_pair(c,make_pair(w,iq)));
        c++;
    }


    sort (elephants.begin(),elephants.end(),sort_pred);




    //int m [1000] = {0};  //made into global
    //parent array made into global variable
    for (int k = 0;k<1001;k++){
        p[k] = -1;
        //cerr<<m[k]<<endl;
    }
    //REMEMBER TO START PARENT LABEL AT 1 !!!!
    for (int i = 0;i<elephants.size();i++){


        int pick  = 0;
        for (int j =0;j<elephants.size();j++){
            if(m[j]>m[i]+pick&&check(elephants[i],elephants[j])){
                pick=m[j];
                p[i] = j; //CHANGE IF NECESSARY
            }
        }
        m[i]+=pick+1;
    }

    int greatest_index = 0;
    for (int i = 0;i<elephants.size();i++){
        if(m[i]>m[greatest_index]) greatest_index = i;

    }
 
    cerr<<m[greatest_index]<<endl;
    print_recurse(greatest_index, p[greatest_index]);

    return 0;
}



/* @END_OF_SOURCE_CODE */

Code: Select all

AC