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

我去! 手写快排 G++ RE C++ TLE

Posted by yajunw2013 at 2014-10-23 19:54:54 on Problem 1002
# include <stdio.h>
# include <ctype.h>
# include <time.h>
# include <stdlib.h>
# include <algorithm>
int a[100005];
int getInt(char *s) {
    int ret = 0;
    for (int i = 0; s[i]; ++i) {
        if (isdigit(s[i])) ret = ret*10 + s[i]-'0';
        else if (isalpha(s[i])) {
            ret = ret*10;
            if (s[i]<='O') ret += (s[i]-'A')/3+2;
            else if (s[i]<='S') ret += 7;
            else if (s[i]<='V') ret += 8;
            else ret += 9;
        }
    }
    return ret;
}
int rpartion(int *arr, int r)
{
    if (r <= 0) return 0;
    int t = rand()%(r+1);
    if (t^r) std::swap(arr[t], arr[r]);
    int x = arr[r];
    int i = -1;
    for (int j = 0; j < r; ++j) {
        if (arr[j]<=x && ++i!=j) {
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[++i], arr[r]);
    return i;
}
void rqsort(int *arr, int n)
{
    if (n>1) {
        int x = rpartion( arr, n-1 );
        rqsort(arr, x);
        rqsort(arr+x+1, n-x-1);
    }
}
int main()
{
    srand(time(NULL));
    int n;
    char s[55];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        a[i] = getInt(s);
    }
    rqsort(a, n);
    bool exist = false;
    for (int i = 0; i < n; ++i) {
        int c = 1;
        while (i+1 < n && a[i] == a[i+1]) ++c, ++i;
        if (c > 1) printf("%03d-%04d %d\n", a[i]/10000, a[i]%10000, c), exist = true;
    }
    if (exist == false) printf("No duplicates.\n");

    return 0;
}

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