oj.uz

Submission #989151

# Submission time Handle Problem Language Result Execution time Memory
989151 2024-05-27T15:43:47 Z khanhphucscratch Minerals (JOI19_minerals) C++14
40 / 100
 176 ms 3152 KB 
#include<bits/stdc++.h>
#include "minerals.h"
using namespace std;
/*int Query(int x)
{
    cout<<"? "<<x<<endl;
    int ans; cin>>ans;
    return ans;
}
void Answer(int a, int b)
{
    cout<<"! "<<a<<" "<<b<<endl;
}*/
set<pair<int, int>> ans;
long long dp[43001], place[43001], pre = 0;
bool state[43001];
int changeQuery(int x)
{
    if(x < 0) return 0;
    state[x] ^= 1;
    int cur = Query(x), a = cur - pre;
    pre = cur;
    return a;
}
void calculate(vector<int> a, vector<int> b, int ex, bool full)
{
    if(a.size() == 1){
        ans.insert({a[0], b[0]});
        return;
    }
    int num = place[a.size()];
    for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
    /*cout<<"We're solving: "<<full<<" "<<ex<<endl;
    for(int i : a) cout<<i<<" ";
    cout<<endl;
    for(int i : b) cout<<i<<" ";
    cout<<endl;
    cout<<"Optimal: "<<num<<endl;*/
    vector<int> al, ar, bl, br;
    for(int i = 0; i < num; i++){
        al.push_back(a[i]);
        if(ex < 0 || i > 0) changeQuery(a[i]);
    }
    for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
    for(int i = 0; i < b.size()-1; i++){
        if((changeQuery(b[i]) == 0) == full) br.push_back(b[i]);
        else bl.push_back(b[i]);
    }
    int last = b[b.size()-1];
    if(bl.size() == al.size()){
        swap(bl, br); swap(al, ar); full ^= 1;
    }
    bl.push_back(last);
    if(full == 0){ //left are 1
        calculate(bl, al, last, (state[last]^1));
        calculate(ar, br, -1, 0);
    }
    else{ //right are 1
        calculate(bl, al, last, (state[last]^1));
        calculate(ar, br, -1, 1);
    }
}
void Solve(int n)
{
    //Calculate dp
    for(int i = 2; i <= n; i++){
        dp[i] = 1e18;
        for(int j = i/4; 2*j <= i; j++){ //pray
            long long val = i+j-1+dp[j]+dp[i-j];
            if(val < dp[i]){dp[i] = val; place[i] = j;}
        }
    }
    vector<int> a, b;
    for(int i = 1; i <= 2*n; i++){
        if(changeQuery(i) == 1) a.push_back(i);
        else b.push_back(i);
    }
    calculate(a, b, -1, 1);
    for(pair<int, int> i : ans) Answer(i.first, i.second);
}

Compilation message

minerals.cpp: In function 'void calculate(std::vector<int>, std::vector<int>, int, bool)':
minerals.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
      |                    ~~^~~~~~~~~~
minerals.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
      |                      ~~^~~~~~~~~~
minerals.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < b.size()-1; i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 14 ms 1368 KB Output is correct
5 Correct 40 ms 2384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 14 ms 1368 KB Output is correct
9 Correct 40 ms 2384 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 21 ms 1660 KB Output is correct
12 Correct 40 ms 2440 KB Output is correct
13 Correct 44 ms 2384 KB Output is correct
14 Correct 38 ms 2648 KB Output is correct
15 Incorrect 176 ms 3152 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -