oj.uz

Submission #487289

# Submission time Handle Problem Language Result Execution time Memory
487289 2021-11-15T03:48:44 Z minhcool Minerals (JOI19_minerals) C++17
40 / 100
 128 ms 5064 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 tot = 0;
/*
int Query(int x){
	tot++;
	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() == 1){
            answer.pb({a[0], b[0]});
            continue;
        }
        int mid = (a.size() + 1) / 2;
        vector<int> a1, b1, a2, b2, a3, b3, a4, b4;
        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]);
    	//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() == 1){
        	answer.pb({a1[0], b1[0]});
        	for(auto it : slices) Query(it);
        	slices.clear();
		}
 		else if(a1.size()){
       		mid = (a1.size() + 1) / 2;
       		int lst;
			for(int i = 0; i < mid; i++){
				lst = Query(a1[i]);
				a3.pb(a1[i]);
				slices.erase(a1[i]);
			}
			for(int i = 0; i < b1.size(); i++){
				int temp = Query(b1[i]);
				slices.erase(b1[i]);
				if(temp == lst){
					b4.pb(b1[i]);
				}
				else{
					b3.pb(b1[i]);
					lst = temp;
				}
			}
			for(int i = mid; i < a1.size(); i++){
				a4.pb(a1[i]);
				slices.erase(a1[i]);
				Query(a1[i]);
			}
			for(auto it : slices) Query(it);
			slices.clear();
			//assert(tol == 0);
		}
		//assert(!tol);
        if(a3.size()) que.push({a3, b3});
        if(a4.size()) que.push({a4, b4});
        if(a2.size()) que.push({a2, b2});
    }
    for(auto it : answer) Answer(it.fi, it.se);
}
/*
void process(){
	int x = 38000;
	for(int i = 1; i <= x * 2; i++){
		co[i] = (i + 1) / 2;
	}
	Solve(x);
	cout << tot << "\n";
}
 
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:101:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
      |                          ~~^~~~~~~~~~
minerals.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 0; i < b.size(); i++){
      |                        ~~^~~~~~~~~~
minerals.cpp:130:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    for(int i = 0; i < b1.size(); i++){
      |                   ~~^~~~~~~~~~~
minerals.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |    for(int i = mid; i < a1.size(); i++){
      |                     ~~^~~~~~~~~~~
minerals.cpp:133:5: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     if(temp == lst){
      |     ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 456 KB Output is correct
2 Correct 5 ms 568 KB Output is correct
3 Correct 11 ms 712 KB Output is correct
4 Correct 27 ms 1340 KB Output is correct
5 Correct 61 ms 2136 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 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 568 KB Output is correct
7 Correct 11 ms 712 KB Output is correct
8 Correct 27 ms 1340 KB Output is correct
9 Correct 61 ms 2136 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 34 ms 1580 KB Output is correct
12 Correct 50 ms 2188 KB Output is correct
13 Correct 40 ms 2204 KB Output is correct
14 Correct 43 ms 2128 KB Output is correct
15 Incorrect 128 ms 5064 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -