oj.uz

답안 #977155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977155 2024-05-07T12:34:08 Z vjudge1 새 집 (APIO18_new_home) C++17
0 / 100
 959 ms 48584 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first

signed main()
{
    int t1,t2,t3,t4;
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,k,q;cin>>n>>k>>q;
	
	priority_queue<pii,vector<pii>,greater<pii>>nummy;
	deque<pii>currpick;
	vector<priority_queue<int,vector<int>,greater<int>>>bytypes(k + 1);
	vector<int>tbp(k+1);
	fill(tbp.begin(),tbp.end(),0);
	
	for (int a=0; a<n; a++)
	{
		cin >> t1 >> t2 >> t3 >> t4;
		nummy.push({t1,t2});
		bytypes[t2].push(t1);
	}
	//cerr << "yay you made it past one!:)\n";
	
	int currhav = 0, tracker = 0;
	
	while ((!nummy.empty()) && currhav < k)
	{
		int currtype = nummy.top().second, currpos = nummy.top().first;
		if (((1 << currtype) & (tracker)) == 0)
		{
			currhav++;
		}
		else
		{
			tbp[currtype]++;
		}
		tracker |= (1<<currtype);
		currpick.push_back(nummy.top());
		bytypes[currtype].pop();
		nummy.pop();
	}
	
	if (currhav < k)
	{
		for (int a = 0; a < q; a++)cout << "-1\n";
	}
	//cout << "past second\n";
	
	cerr << "tracker : " << tracker << " " << currhav << "\n";
	cerr << "outputting start queue:\n";
	vector<pii>temp1(currpick.begin(),currpick.end());
	for(auto x:temp1)
	{
		cerr<<x.first<<" ";
	}
	cerr << "\ndone\n";
	
	while (tbp[currpick.front().second]>0)
	{
		tbp[currpick.front().second]--;
		currpick.pop_front();
	}
	
	priority_queue<int,vector<int>,greater<int>>queries;
	
	for (int a=0; a < q; a++)
	{
		cin >> t1 >> t2;
		queries.push(t1);
	}
	
	while (!queries.empty())
	{
		//cout << "query " << queries.top() << ":\n";
		int currat = queries.top();queries.pop();
		//enter till reach currentque
		while ((!nummy.empty())&& nummy.top().first <= currat)
		{
			currpick.push_back(nummy.top());
			int currtype = nummy.top().second;
			bytypes[currtype].pop();
			tbp[currtype]++;
			nummy.pop();
			//cerr<<"pushing in at till u reach me " << currpick.back().first << "\n";
		}
		int currtype = currpick.front().second;
		
		//popping
		while (tbp[currtype] > 0)
		{
			//cerr<<"popping out  " << currpick.front().first << "\n";
			currpick.pop_front();
			tbp[currtype]--;
			currtype = currpick.front().second;
		}
		//while next is more zhide
		while ((!bytypes[currtype].empty()) && (abs(bytypes[currtype].top() - currat) < abs(currpick.front().first - currat)))
		{
			while (nummy.top().second != currtype)
			{
				//cerr<<"pushing in at just getting the better ones" << nummy.top().first << "\n";
				currpick.push_back(nummy.top());
				bytypes[nummy.top().second].pop();
				tbp[nummy.top().second]++;
				nummy.pop();
				currtype = currpick.front().second;
			}
			//cerr<<"pushing in at just getting the better ones" << nummy.top().first << "\n";
			currpick.push_back(nummy.top());
			bytypes[nummy.top().second].pop();
			tbp[nummy.top().second]++;
			nummy.pop();
			currtype = currpick.front().second; 
			while (tbp[currtype] > 0)
			{
				//cerr<<"popping out  " << currpick.front().first << "\n";
				currpick.pop_front();
				tbp[currtype]--;
				currtype = currpick.front().second;
			}  
		}
		currtype = currpick.front().second;
		//popping
		while (tbp[currtype] > 0)
		{
			//cerr<<"popping out  " << currpick.front().first << "\n";
			currpick.front();
			tbp[currtype]--;
			currtype = currpick.front().second;
		}
		cout << max(abs(currpick.back().first - currat), abs(currpick.front().first-currat)) << "\n";;
	}
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:33:38: warning: unused variable 'currpos' [-Wunused-variable]
   33 |   int currtype = nummy.top().second, currpos = nummy.top().first;
      |                                      ^~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -