Submission #854335

#	Time	Username	Problem	Language	Result	Execution time	Memory
854335		Juan	Through Another Maze Darkly (CCO21_day1problem3)	C++17	0 / 25	14 ms	19868 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tii tuple<int,int,int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int maxn = 8e5+5, INF=0x3f3f3f3f, MOD=1e9+7;

vector<int> adj[maxn];

int32_t main(){
	int n,q; cin >> n >> q;
	for(int i=1; i<=n; i++){
		int s; cin >> s;
		for(int j=0; j<s; j++){
			int a; cin >> a;
			adj[i].push_back(a);
		}
	}

	vector<int> spin(n+1);
	for(int i=1; i<=n; i++){
		if(adj[i].size()==1 || adj[i][0]<adj[i][1]) spin[i]=true;
		else spin[i]=false;
	}

	vector<pii> queries;
	for(int i=0; i<q; i++){
		int k; cin >> k;
		queries.pb({k,i});
	}
	sort(all(queries), greater<pii>());

	vector<int> ans(q);
	int cnt=0;
	while(queries.size() && queries.back().ff==0){
		ans[queries.back().ss]=1, queries.pop_back();
	}
	for(int i=1; i<=n; i++){
		if(spin[i]){
			cnt++;
			while(queries.size() && queries.back().ff==cnt)
				ans[queries.back().ss]=i+1-2*(i==n), queries.pop_back();
		}
		else{
			cnt += 2*(i-1);
			while(queries.size() && queries.back().ff<=cnt){
				auto[k,id] = queries.back();

				// cout << cnt << "-" << k << endl;

				if(cnt-k<=i-1) ans[id] = i-(cnt-k);
				else ans[id] = 1+(cnt-k)-(i-1);
				queries.pop_back();
			}
			cnt++;
		}
	}

	while(queries.size()){
		auto[k,id] = queries.back();
		k-=cnt;
		k %= 2*(n-1);
		if(k<=n-1) ans[id] = 1+k;
		else ans[id] = 1+k-(n-1);
		queries.pop_back();
	}

	for(int x : ans) cout << x << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5