oj.uz

답안 #854338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854338 2023-09-26T21:02:05 Z Juan Through Another Maze Darkly (CCO21_day1problem3) C++17
0 / 25
 13 ms 19928 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()){
		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
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 5.0

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