Я использовал Skip-List с соотношением 10/10000.
Список из 10 элементов, а в списке масив из из 10000 элементов (чтобы ускорить удоление). Время работы где-то O(N*log n*log n) (0.671 сек).
| Код |
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <assert.h>
#define FOR(i,to) for (int i = 0; i < int(to); ++i)
#define FOR1(i,to) for (int i = 1; i < int(to); ++i)
#define FORN(i,from,to) for (int i = (from); i < int(to); ++i)
#define SZ(c) int((c).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()
#define FREE(a) memset(a, 0, sizeof a)
using namespace std;
typedef vector<int> VI;
typedef vector<bool> VB;
typedef vector<string> VS;
const double PI = acos(-1.0);
const int INF = 1e10;
const double EPS = 1e-10;
inline void openfiles()
{
freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
}
inline void print(int num)
{
char s[9];
int l = 0;
while (num)
s[l++] = num % 10, num /= 10;
while (l--)
putc('0' + s[l], stdout);
putc(' ', stdout);
}
int n, k;
list<vector<int> > l;
int main ()
{
#ifndef ONLINE_JUDGE
openfiles();
#endif
scanf("%d %d", &n, &k);
int capasity = 10000;
vector<int> v;
FOR(i,n)
{
v.PB(i+1);
if (SZ(v)==capasity)
{
l.PB(v);
v.clear();
}
}
l.PB(v);
int pos = k-1;
list<vector<int> >::iterator intr = l.begin();
while (pos>=SZ(*intr))
{
pos -= SZ(*intr);
if (SZ(*intr) == 0){
l.erase(intr++);
}else{
intr++;
}
if (intr == l.end())
intr = l.begin();
if (l.empty())
break;
if (SZ(l) == 1)
pos = pos % SZ(*intr);
}
FOR(i,n)
{
print((*intr)[pos]);
(*intr).erase((*intr).begin()+pos);
pos = (pos + k-1);
++count;
while (pos>=SZ(*intr))
{
if (SZ(*intr) == 0){
l.erase(intr++);
}else{
pos -= SZ(*intr);
intr++;
}
if (intr == l.end())
intr = l.begin();
if (l.empty() || (SZ(l) == 1 && SZ(*intr)==0))
break;
if (SZ(l) == 1)
pos = pos % SZ(*intr);
}
}
return 0;
}
|
|
Максимум чуть больше 6*10^9. 
Бактерий наверное бывает, но они врядли в детские считалки играют 
и моим алгоритмом уж точно пользоваться не будут
