Submission #283713

#	Time	Username	Problem	Language	Result	Execution time	Memory
283713		AMO5	Tenis (COI19_tenis)	C++17	18 / 100	1092 ms	18216 KiB

tenis

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=1e5+5;
bool DEBUG=0;

int n,q;
int a[3][mxn];
map<int,int>pos[3];

//subtask 1,2,3
bool vis[mxn];

void dfs(int u, int now){
	if(vis[u]==1)return;
	//cerr<<" dfs "<<now<<" "<<u<<" \n";
	vis[u]=1;
	for(int i=0; i<3; i++){
		if(i==now)continue;
		for(int j=0; j<pos[i][u]; j++){
			int v = a[i][j];
			dfs(v,i);
		}
	}
	return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>n>>q;
    for(int i=0; i<3; i++){
		for(int j=0; j<n; j++){
			cin>>a[i][j];
			a[i][j]--;
			pos[i][a[i][j]]=j;
		}
	}
	bool need=1;
	while(q--){
		int typ;
		cin>>typ;
		if(typ==1){
			int x; cin>>x;
			x--;
			if(need){
				fill(vis,vis+n,0);
				for(int i=0; i<3; i++){
					dfs(a[i][0],i);
				}
				need=0;
				/*
				for(int i=0; i<n; i++){
					cerr<<vis[i]<<" ";
				}
				cerr<<"\n";
				*/ 
			}
			if(vis[x]){
				cout<<"DA \n";
			}else{
				cout<<"NE \n";
			}
		}else{
			need=1;
			int p,x,y;
			cin>>p>>x>>y;
			p--; x--; y--;
			int posx = pos[p][x];
			int posy = pos[p][y];
			swap(a[p][posx],a[p][posy]);
			swap(pos[p][x],pos[p][y]);
		}
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49