oj.uz

Submission #854339

# Submission time Handle Problem Language Result Execution time Memory
854339 2023-09-26T21:10:36 Z Juan Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 913 ms 97844 KB 
#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]){
			if(i==n) continue;
			cnt++;
			while(queries.size() && queries.back().ff==cnt)
				ans[queries.back().ss]=i+1, 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();
			}

			if(i!=n) cnt++;
			while(queries.size() && queries.back().ff==cnt)
				ans[queries.back().ss]=i+1, queries.pop_back();
		}
	}

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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 14 ms 19896 KB Output is correct
3 Correct 107 ms 28312 KB Output is correct
4 Correct 833 ms 94960 KB Output is correct
5 Correct 913 ms 97564 KB Output is correct
6 Correct 896 ms 97844 KB Output is correct
7 Correct 360 ms 53648 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 19292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 14 ms 19896 KB Output is correct
3 Correct 107 ms 28312 KB Output is correct
4 Correct 833 ms 94960 KB Output is correct
5 Correct 913 ms 97564 KB Output is correct
6 Correct 896 ms 97844 KB Output is correct
7 Correct 360 ms 53648 KB Output is correct
8 Incorrect 5 ms 19292 KB Output isn't correct
9 Halted 0 ms 0 KB -