题解 | 坠落的蚂蚁

硬模拟，不知为何就是有一个用例没通过 19/20

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;

struct ant {
	int pos;
	int dir;
	bool visit;
};

struct record {
	int count;
	vector<int> arrindex;
};

int main() {
	int N,index=-1;
	vector<ant> arr;
	scanf("%d",&N);
	for (int i = 0; i < N; i++) {
		int a,  b;
		scanf(" %d%d",&a,&b);
		arr.push_back({a,b,0});
		if(b==0)
			index=i;			
	}
	int t=0;
	record rec[101];
	for (int i = 0; i <= 100; i++) {
		rec[i].count = 0;
		rec[i].arrindex.clear();
	}
	for (int i = 0; i < N; i++) {
		rec[arr[i].pos].count++;
		rec[arr[i].pos].arrindex.push_back(i);
	}

	while (1) {
 		if(arr[index].pos==0||arr[index].pos==100) //fall
			break;
		//precheck
		for (int i = 0; i < N; i++)
		{
			arr[i].visit=false;
		}
		for (int i = 1; i < 100; i++) {
			if (rec[i + 1].count >= 1 && rec[i].count  >= 1) {
				//rec[i + 1].arrindex[0]
				int jv=-1, kv=-1;
				for (int j = 0; j < rec[i + 1].arrindex.size(); j++) {
					if (arr[rec[i + 1].arrindex[j]].dir == -1) {
						jv=j;
						break;
					}
						
				}for (int k = 0; k < rec[i].arrindex.size(); k++) {
					if (arr[rec[i].arrindex[k]].dir == 1) {
						kv=k;
						break;
					}
				}
				if (kv >= 0 && jv >= 0 && kv < rec[i].arrindex.size() && jv < rec[i + 1].arrindex.size() && arr[rec[i + 1].arrindex[jv]].visit==false && arr[rec[i].arrindex[kv]].visit==false) {
					swap(arr[rec[i + 1].arrindex[jv]].dir, arr[rec[i].arrindex[kv]].dir);
					swap(arr[rec[i + 1].arrindex[jv]].pos, arr[rec[i].arrindex[kv]].pos);
					arr[rec[i + 1].arrindex[jv]].visit=true;
					arr[rec[i].arrindex[kv]].visit = true;
				}
			}
		}
		for (int i = 0; i <= 100; i++) {
			rec[i].count = 0;
			rec[i].arrindex.clear();
		}
		t++; //start moving
		for (int i = 0; i < N; i++) {
			if (arr[i].dir == 1 && arr[i].pos!=0 && arr[i].pos != 100) {
				++arr[i].pos;
				rec[arr[i].pos].count++;
				rec[arr[i].pos].arrindex.push_back(i);
			}	
			else if(arr[i].dir==-1 && arr[i].pos != 0 && arr[i].pos != 100){
				--arr[i].pos;
				rec[arr[i].pos].count++;
				rec[arr[i].pos].arrindex.push_back(i);
			}
			else if (arr[i].dir == 0 && arr[i].pos != 0 && arr[i].pos != 100) {
				rec[arr[i].pos].count++;
				rec[arr[i].pos].arrindex.push_back(i);
			}
		}
		//check
		int remain=0;
		for(int i=1;i<100;i++){
			if (rec[i].count == 2) {
				swap(arr[rec[i].arrindex[0]].dir,arr[ rec[i].arrindex[1]].dir);
			}
			else if (rec[i].count == 3) {
				for (int j = 0; j < 3; j++) {
					if (arr[rec[i].arrindex[j]].dir == 0) {
						vector<int>::iterator it = rec[i].arrindex.begin() + j;
						rec[i].arrindex.erase(it);
						swap(arr[rec[i].arrindex[0]].dir, arr[rec[i].arrindex[1]].dir);
					}
				}
			}
			//if (rec[i + 1].count == 1 && rec[i].count == 1) {
			//	//rec[i + 1].arrindex[0]
			//	if (arr[rec[i + 1].arrindex[0]].dir == -1 && arr[rec[i].arrindex[0]].dir == 1) {
			//		swap(arr[rec[i+1].arrindex[0]].dir, arr[rec[i].arrindex[0]].dir);
			//		swap(arr[rec[i + 1].arrindex[0]].pos, arr[rec[i].arrindex[0]].pos);
			//	}	
			//}
		}
		int other=0;
		for (int i = 1; i < 100; i++) {
			if(rec[i].count == 1)
				remain++;
			if(rec[i].count != 0)
				other++;
		}
		if (remain == 1 && other==1 && arr[index].pos > 0 && arr[index].pos < 100) {
			printf("Cannot fall!\n");
			return 0;
		}
	}	
	printf("%d\n",t);
	return 0;
}