oj.uz

답안 #1041587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041587 2024-08-02T06:00:08 Z vjudge1 Tenis (COI19_tenis) C++17
30 / 100
 317 ms 12312 KB 
#warning Check FastIO
#ifdef ONLINE_JUDGE
    #pragma GCC optimize("Ofast")
    #pragma GCC target("avx,avx2,fma")
#endif
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <random>
#include <chrono>
#include <iomanip>
#include <vector>
#include <fstream>
using namespace std;
#define vll vector<ll>
#define sll set<ll>
#define vstr vector<string>
#define ll long long
#define ld long double
#define supra main
#define pb push_back
#define add insert
#define rall(x) rbegin(x),rend(x)
#define all(x) (x).begin(),(x).end()
#define I ios_base::sync_with_stdio(false);
#define Hear cin.tie(NULL);
#define Shots cout.tie(NULL);
#define Ratatatata
#define bits_on(a) (__builtin_popcountll(a))
#define mx_pw2(a) (__builtin_ctzll(a))
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUFFLE(v) shuffle(all(v), RNG); 
const ll inf=LLONG_MAX;
void input(vll& a)
{
    for(auto& i:a)
        cin>>i;
}
void pyn(bool a)
{
    cout<<(a?"YES":"NO")<<endl;
}
ll powmod(ll a,ll b,ll modulo)
{
  if(b==0){
    return 1;
  }
  ll temp=powmod(a,b/2,modulo);
  if(b%2==0){
    return (temp*temp)%modulo;
  }
  else{
    return (a*((temp*temp)%modulo))%modulo;
  }
}

bool Prime(ll n){
    for (ll i = 2; i*i <= n; i++)
        if (n % i == 0)
            return false;
    return (n>1);
}
const int N=1e5+10;
ll rank_of[N][3];
bool can_win[N];
void solve()
{
	ll n,q;
	cin>>n>>q;	
	vector<int> p[3];
	for(int j=0;j<3;j++)
	{
		for(int i=0;i<n;i++)
		{
			ll x;
			cin>>x;
			if(i==0)
				can_win[x]=1;
			p[j].push_back(x);
			rank_of[x][j]=n-i;
		}
	}
	for(int it=0;it<353;it++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=n-2;k>=0;k--)
			{
				can_win[p[j][k]]|=can_win[p[j][k+1]];
			}
		}
	}
	bool change=0;
	while(q--)
	{
		ll type;
		cin>>type;
		if(type==1)
		{
			ll x;
			cin>>x;
			if(!change)
			{
				if(can_win[x])
				{
					cout<<"DA"<<endl;
				}
				else
				{
					cout<<"NE"<<endl;
				}
				continue;
			}
			ll skill[3];
			skill[0]=rank_of[x][0];
			skill[1]=rank_of[x][1];
			skill[2]=rank_of[x][2];
			bool change=1;
			vector<pair<ll,ll>> oth[3];
			int ind[3];
			for(int j=0;j<3;j++)
			{
				ind[j]=0;
				for(int i=1;i<=n;i++)
				{
					oth[j].push_back({rank_of[i][j],i});
				}
				sort(begin(oth[j]),end(oth[j]));
			}
			ll kills=0;
			while(change)
			{
				change=0;
				for(int i=0;i<3;i++)
				{
					if(ind[i]<oth[i].size())
					{
						auto it=oth[i][ind[i]];
						if(it.first<skill[i])
						{
							// We nailed it
							change=1;
							ll mp=it.second;
							kills++;
							skill[0]=max(skill[0],rank_of[mp][0]);
							skill[1]=max(skill[1],rank_of[mp][1]);
							skill[2]=max(skill[2],rank_of[mp][2]);
							ind[i]++;
						}
					}
				}
			}
			// cout<<"Query for "<<kills<<' '<<skill[0]<<' '<<skill[1]<<' '<<skill[2]<<endl;
			if(max({skill[0],skill[1],skill[2]})==n)
			{
				cout<<"DA"<<endl;
			}
			else
			{
				cout<<"NE"<<endl;
			}
		}
		else
		{
			change=1;
			ll tp,x,y;
			cin>>tp>>x>>y;
			tp--;
			swap(rank_of[x][tp],rank_of[y][tp]);
		}
	}
}
int supra(){
    I Hear Shots Ratatatata
    ll tqwertyuiop=1;
    for(int tp=1;tp<=tqwertyuiop;tp++)
    {
        // cout<<"Case #"<<tp<<": ";
        solve();
    }
    return 0;
}
/*
Bro use only in a emergency 
this is kind of hacking
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
*/

Compilation message

tenis.cpp:1:2: warning: #warning Check FastIO [-Wcpp]
    1 | #warning Check FastIO
      |  ^~~~~~~
tenis.cpp: In function 'void solve()':
tenis.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |      if(ind[i]<oth[i].size())
      |         ~~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 254 ms 10836 KB Output is correct
14 Correct 261 ms 10716 KB Output is correct
15 Correct 254 ms 10744 KB Output is correct
16 Correct 294 ms 10724 KB Output is correct
17 Correct 296 ms 10788 KB Output is correct
18 Correct 304 ms 10816 KB Output is correct
19 Correct 317 ms 12312 KB Output is correct
20 Correct 193 ms 4192 KB Output is correct
21 Correct 274 ms 12176 KB Output is correct
22 Correct 280 ms 10780 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 4316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 254 ms 10836 KB Output is correct
14 Correct 261 ms 10716 KB Output is correct
15 Correct 254 ms 10744 KB Output is correct
16 Correct 294 ms 10724 KB Output is correct
17 Correct 296 ms 10788 KB Output is correct
18 Correct 304 ms 10816 KB Output is correct
19 Correct 317 ms 12312 KB Output is correct
20 Correct 193 ms 4192 KB Output is correct
21 Correct 274 ms 12176 KB Output is correct
22 Correct 280 ms 10780 KB Output is correct
23 Incorrect 288 ms 4316 KB Output isn't correct
24 Halted 0 ms 0 KB -