fork download
copy 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 123456
  13. #define MAX 1037471823
  14. #define Q 103
  15.  
  16. using namespace std;
  17.  
  18. struct node
  19. {
  20. 	int x, y, z;
  21. 	bool operator < (const node &k) const { return x < k.x || (x == k.x && y < k.y) || (x == k.x && y == k.y && z < k.z); }
  22. } k[MS];
  23. char st[MS];
  24. int s[MS], l, r[MS], o, a;
  25.  
  26. int main()
  27. {
  28. 	scanf("%s", st); l = strlen(st);
  29. 	rep(i, 1, l) s[i] = int(st[i-1]);
  30. 	s[0] = s[l];
  31. 	rep(i, 1, l) k[i].x = s[i], k[i].y = 0, k[i].z = i;
  32. 	sort(k+1, k+1+l); rep(i, 1, l) if (k[i].x == k[i-1].x && k[i].y == k[i-1].y) r[k[i].z] = r[k[i-1].z]; else r[k[i].z] = i;
  33. 	o = 1;
  34. 	while (true)
  35. 	{
  36. 		rep(i, 1, l) k[i].x = r[k[i].z], k[i].y = r[(k[i].z+o-1)%l+1];
  37. 		a = 1; rep(i, 2, l+1) if (k[i-1].x != k[i].x)
  38. 		{
  39. 			if (i-1 > a) sort(k+a, k+i);
  40. 			a = i;
  41. 		}
  42. 		rep(i, 1, l) if (k[i].x == k[i-1].x && k[i].y == k[i-1].y) r[k[i].z] = r[k[i-1].z]; else r[k[i].z] = i;
  43. 		if (o > l) break;
  44. 		o *= 2;
  45. 	}
  46. 	rep(i, 1, l) printf("%c", s[k[i].z-1]);
  47. 	printf("\n");
  48. 	return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5836KB
comments (?)
stdin
copy 
JSOI07
stdout
copy 
I0O7SJ
https://ideone.com/3ttjua
BZOJ 1031
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!