oj.uz

답안 #283708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283708 2020-08-26T05:55:45 Z AMO5 Tenis (COI19_tenis) C++17
18 / 100
 500 ms 18424 KB 
#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];
map<int,bool>vis2[3];

void dfs(int u, int now){
	if(vis2[now][u]==1)return;
	//cerr<<" dfs "<<now<<" "<<u<<" \n";
	vis2[now][u]=1;
	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++)vis2[i]=map<int,bool>();
				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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 26 ms 640 KB Output is correct
8 Correct 16 ms 640 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 27 ms 628 KB Output is correct
12 Correct 4 ms 512 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 26 ms 640 KB Output is correct
8 Correct 16 ms 640 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 27 ms 628 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Execution timed out 1092 ms 17912 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 18424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 26 ms 640 KB Output is correct
8 Correct 16 ms 640 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 27 ms 628 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Execution timed out 1092 ms 17912 KB Time limit exceeded
14 Halted 0 ms 0 KB -