oj.uz

답안 #487277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487277 2021-11-15T02:37:04 Z minhcool Minerals (JOI19_minerals) C++17
40 / 100
 98 ms 5056 KB 
#include<minerals.h>
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, a[N];
 
set<int> slices;
 
vector<int> le, ri;
 
vector<ii> answer;
 
queue<pair<vector<int>, vector<int>>> que;

int arr[N];

bool ck[N];

int co[N];

int cnt[N], tol = 0;
/*
int Query(int x){
	if(!ck[x]){
		ck[x] = 1;
		if(cnt[co[x]] == 0){
			tol++;
		}
		cnt[co[x]]++;
	}
	else{
		ck[x] = 0;
		if(cnt[co[x]] == 1){
			tol--;
		}
		cnt[co[x]]--;
	}
	return tol;
}

void Answer(int x, int y){
	assert(co[x] == co[y]);
	assert(x != y);
}*/
 
void Solve(int N){
    n = N;
    le.clear();
    ri.clear();
    slices.clear();
    answer.clear();
    int lst = 0;
    for(int i = 1; i <= 2 * n; i++){
        int temp = Query(i);
        slices.insert(i);
        if(lst < temp){
            le.pb(i);
        }
        else{
            ri.pb(i);
        }
        lst = temp;
    }
    for(int i = 1; i <= 2 * n; i++) Query(i);
    slices.clear();
    //vector<int> 
    que.push({le, ri});
    //return;
    while(!que.empty()){
        vector<int> a = que.front().fi, b = que.front().se;
        //cout << a.size() << "\n";
        que.pop();
        //assert(a.size() == b.size());
        if(a.size() != b.size()){
        	cout << "DCM CUOC DOI\n";
        	return;
		}
        if(a.size() == 1){
            answer.pb({a[0], b[0]});
            continue;
        }
        int mid = (a.size() + 1) / 2;
        vector<int> a1, b1, a2, b2;
        for(int i = 0; i < mid; i++){
            Query(a[i]);
            slices.insert(a[i]);
            a1.pb(a[i]);
        }
        for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
        int sum = 0;
        for(int i = 1; i <= 2 * n; i++) sum += (ck[i] == 1);
    	//cout << sum << "\n";
    	//cout << tol << "\n";
        int lst = slices.size();
        for(int i = 0; i < b.size(); i++){
            int temp = Query(b[i]);
            //cout << temp << "\n";
            slices.insert(b[i]);
            if(temp != lst){
                b2.pb(b[i]);
                lst = temp;
            }
            else b1.pb(b[i]);
        }
        for(auto it : slices) Query(it);
        slices.clear();
        if(a1.size() != b1.size() || a2.size() != b2.size()){
        	//cout << a1.size() << " " << b1.size() << " " << a2.size() << " " << b2.size() << "\n";
        	cout << "DAMN\n";
        	return;
		}
        if(a1.size()) que.push({a1, b1});
        if(a2.size()) que.push({a2, b2});
    }
    for(auto it : answer) Answer(it.fi, it.se);
}
/*
void process(){
	int x = 3;
	for(int i = 1; i <= x * 2; i++){
		co[i] = (i + 1) / 2;
	}
	Solve(x);
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}*/

Compilation message

minerals.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
      |                          ~~^~~~~~~~~~
minerals.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i = 0; i < b.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 456 KB Output is correct
2 Correct 5 ms 584 KB Output is correct
3 Correct 12 ms 932 KB Output is correct
4 Correct 29 ms 1420 KB Output is correct
5 Correct 53 ms 2396 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 5 ms 584 KB Output is correct
7 Correct 12 ms 932 KB Output is correct
8 Correct 29 ms 1420 KB Output is correct
9 Correct 53 ms 2396 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 32 ms 1704 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 46 ms 2548 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 98 ms 5056 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -