[CodeForces653F]Ants on a Circle

Title Link

Click to open the link

Problem solving

By observing the movement of ants, we can find the following things:

  1. The order of ants does not change.
  2. The final position of ants is the final position of "two ants meet and penetrate". So we can figure out where the ants are in the end.

So now we can know the final position of ants and the order of ants. However, there are \ (n\) ant location schemes that meet the final location and order (because they are rings, they can be transferred to \ (n\). So you need to know which one the final result corresponds to.

Now define the arrangement corresponding to a ring as follows: the number of each ant clockwise from 0. As long as an ant moves from position m-1 to position 0, the arrangement will rotate to the right. If an ant moves from position 0 to position m-1, the arrangement will change to the left wheel. Therefore, it is only necessary to find out how many times each ant passes through 0 along / backward. In fact, this number is equivalent to the number of times that "the ant passes through 0 after meeting" along and backward. In this way, we can find out which rotation is. That's it.

summary

  • Consider rotation as a whole (macro thinking), rather than seeking the final position of an ant (although it can be done, it is particularly troublesome) (micro thinking).

code

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
ll n, m, pp[N], ans[N];
ll t;
struct ANT {
	ll pos, dir, id;
	bool operator < (const ANT &d) const { return pos < d.pos; }
} ant[N];
ll Get(ll x) {
	if (ant[x].dir == -1) {
//		if (t >= ant[x].pos && ant[x].pos != 0)
//			return ((t - ant[x].pos) / m + 1);
//		else if (ant[x].pos == 0)
//			return (t - ant[x].pos) / m;
//		else return 0; 
		return (t - ant[x].pos + m - 1) / m;
	} else {
		if (t >= m - ant[x].pos)
			return -((t - (m - ant[x].pos)) / m + 1);
		else return 0;
//		return - (t + ant[x].pos) / m;
	}
}
int main() {
	scanf("%lld%lld%lld", &n, &m, &t);
	for (ll i = 0; i < n; ++i) {
		scanf("%lld", &ant[i].pos);
		--ant[i].pos;
		char dd = getchar();
		while (dd == ' ') dd = getchar();
		ant[i].dir = (dd == 'L') ? -1 : 1;
		ant[i].id = i;
	}
	sort(ant, ant + n);
	for (ll i = 0; i < n; ++i)
		pp[i] = ((t * ant[i].dir + ant[i].pos) % m + m) % m;
	sort(pp, pp + n);
	ll bg = 0;
	for (ll i = 0; i < n; ++i)
		bg = (Get(i) + bg) % n;
	bg = (bg + n) % n;
	for (ll i = bg, j = 0; j < n; ++j, i = (i + 1) % n)
		ans[ant[i].id] = pp[j];
	for (ll i = 0; i < n; ++i)
		printf("%lld ", ans[i] + 1);
	printf("\n");
	return 0;
}

Posted by overlordhu on Mon, 30 May 2022 01:01:06 +0530