oj.uz

답안 #1041590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041590 2024-08-02T06:01:30 Z vjudge1 Tenis (COI19_tenis) C++17
30 / 100
 420 ms 12464 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<500;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 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 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 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 516 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 516 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 516 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 516 KB Output is correct
13 Correct 362 ms 10712 KB Output is correct
14 Correct 366 ms 10688 KB Output is correct
15 Correct 368 ms 10712 KB Output is correct
16 Correct 416 ms 10728 KB Output is correct
17 Correct 406 ms 12464 KB Output is correct
18 Correct 393 ms 10812 KB Output is correct
19 Correct 420 ms 10876 KB Output is correct
20 Correct 297 ms 4332 KB Output is correct
21 Correct 374 ms 10856 KB Output is correct
22 Correct 375 ms 10776 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 378 ms 4568 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 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 516 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 516 KB Output is correct
13 Correct 362 ms 10712 KB Output is correct
14 Correct 366 ms 10688 KB Output is correct
15 Correct 368 ms 10712 KB Output is correct
16 Correct 416 ms 10728 KB Output is correct
17 Correct 406 ms 12464 KB Output is correct
18 Correct 393 ms 10812 KB Output is correct
19 Correct 420 ms 10876 KB Output is correct
20 Correct 297 ms 4332 KB Output is correct
21 Correct 374 ms 10856 KB Output is correct
22 Correct 375 ms 10776 KB Output is correct
23 Incorrect 378 ms 4568 KB Output isn't correct
24 Halted 0 ms 0 KB -