oj.uz

Submission #989142

# Submission time Handle Problem Language Result Execution time Memory
989142 2024-05-27T15:30:55 Z khanhphucscratch Minerals (JOI19_minerals) C++14
40 / 100
 128 ms 2896 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;
int dp[43001], place[43001], pre = 0;
bool state[43001];
int changeQuery(int x)
{
    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] = 1e9;
        for(int j = i/4; 2*j <= i; j++){ //pray
            int 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:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
      |                    ~~^~~~~~~~~~
minerals.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
      |                      ~~^~~~~~~~~~
minerals.cpp:44:22: 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 = 0; i < b.size()-1; i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
3 Correct 5 ms 988 KB Output is correct
4 Correct 15 ms 1368 KB Output is correct
5 Correct 43 ms 2212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 2 ms 600 KB Output is correct
7 Correct 5 ms 988 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 43 ms 2212 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 22 ms 1652 KB Output is correct
12 Correct 31 ms 2300 KB Output is correct
13 Correct 34 ms 2392 KB Output is correct
14 Correct 31 ms 2384 KB Output is correct
15 Incorrect 128 ms 2896 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -