Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

O(n)的算法为啥会tle...

Posted by pityhero at 2020-04-26 13:41:20 on Problem 2085
答案应该是对的,复杂度也只有O(n),在自己机子上试50000 12497500也能秒出正确结果.为啥C++ G++全是TLE...

#include<cmath>
#include<iostream>
#include<string>
#include<deque>
#include<sstream>
#include<cstdio>
#define EPS 1e-8
inline std::string to_string(int x){
	std::string a;
	while (x>0){
		a = (char)(x%10+'0') + a;
		x/=10;
	}
	return a;
}
int main(){
	int n; long long m;
	while (scanf("%d %Ld",&n,&m)==2&&n!=-1){
		std::string res;
		float l = (1+sqrt(1.0+8.0*m))/2;
		long lb = (int)l+1;
		for (int i=1;i<=n-lb;i++) {
			res+=to_string(i);
			res+=' ';
		}
		std::deque<int> q;
		if (fabs(l-lb)<=EPS) for (int i=n;i>=n-lb+1;i--) q.push_back(i);
		else{
			int kn = m - (lb-1)*(lb-2)/2;
			int frt = kn+n-lb+1;
			for (int i=n;i>=n-lb+1;i--) {
				if (i==frt) q.push_front(i);
				else q.push_back(i);
			}
		}
		for (std::deque<int>::iterator ptr = q.begin(); ptr<q.end()-1;ptr++) {
			res+=to_string(*ptr);
			res+=' ';
		}
		res+=to_string(*(q.end()-1));
		printf("%s\n",res.c_str());
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator