# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
629013 | welleyth | Minerals (JOI19_minerals) | C++17 | 34 ms | 2488 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "minerals.h"
#include <vector>
#include <fstream>
#include <map>
void Solve(int N) {
int col[2*N+1];
for(int i = 0; i < 2*N+1; i++){
col[i] = 0;
}
int c = 0;
int in[N+1];
for(int i = 0; i <= N; i++)
in[i] = 0;
int pos[N+1];
bool is[2*N+1];
bool was[2*N+1];
for(int i = 0; i <= 2*N; i++) in[i] = was[i] = false;
int sz = 0;
int mx[2*N+1];
for(int i = 0; i <= 2*N; i++) mx[i] = 0;
int cnt[2*N+1];
for(int i = 0; i <= 2*N; i++) cnt[i] = 0;
for(int i = 1; i <= 2*N; i++){
int cur = Query(i);
if(cur != sz){
sz = cur;
pos[cur] = i;
is[i] = 1;
in[cur] = 1;
col[i] = sz;
was[i] = true;
} else {
sz = Query(i);
}
mx[i] = sz;
}
cnt[0] = N;
bool answered[N+1];
for(int i = 0; i <= N; i++)
answered[i] = false;
for(int bt = 0; (1 << bt) <= N; bt++){
for(int i = 1; i <= N; i++){
if(answered[i])
continue;
if(in[i] && (i >> bt & 1) == 0){
sz = Query(pos[i]);
in[i] = false;
}
if(!in[i] && (i >> bt & 1) == 1){
sz = Query(pos[i]);
in[i] = true;
}
}
std::map<int,int> gp;
for(int i = 1; i <= 2*N; i++){
if(was[i])
continue;
if(mx[i] < (1 << bt)){
gp[col[i]] = i;
continue;
}
int nw = Query(i);
if(nw == sz){
cnt[col[i]]--;
col[i] |= (1 << bt);
cnt[col[i]]++;
}
gp[col[i]] = i;
sz = Query(i);
}
for(int i = 1; i <= N; i++){
if(cnt[i] == 1 && !answered[i]){
// printf("pair %d %d\n",gp[i],pos[i]);
Answer(gp[i],pos[i]);
answered[i] = true;
was[gp[i]] = true;
if(in[i]){
sz = Query(pos[i]);
}
}
}
}
// for(int i = 1; i <= 2*N; i++){
// printf("col[%d] = %d\n",i,col[i]);
// }
std::vector<int> A[N+1];
for(int i = 1; i <= 2*N; i++){
A[col[i]].push_back(i);
}
for(int i = 1; i <= N; i++){
if(!answered[i])
Answer(A[i][0],A[i][1]);
}
return;
}
/**
4
1 5
2 6
3 4
7 8
**/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |