oj.uz

Submission #841371

# Submission time Handle Problem Language Result Execution time Memory
841371 2023-09-01T15:05:40 Z LucaIlie Minerals (JOI19_minerals) C++17
40 / 100
 17 ms 2988 KB 
#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 43000;
int pairr[2 * MAX_N + 1], perm[2 * MAX_N + 1];
bool inSet[2 * MAX_N + 1];
vector<int> firstt, secondd;
int ans = 0;

void solve( int n ) {
    for ( int b = log2( n ); b >= 0; b-- ) {
        int g1 = 0;
        for ( int i = 0; i < n; i++ ) {
            if ( (i & (1 << b)) ) {
                if ( !inSet[firstt[i]] ) {
                    ans = Query( firstt[i] );
                    inSet[firstt[i]] = true;
                }
            } else {
                g1++;
                if ( inSet[firstt[i]] ) {
                    ans = Query( firstt[i] );
                    inSet[firstt[i]] = false;
                }
            }
        }

        for ( int i = 0; i < n; i++ ) {
            if ( g1 == 0 ) {
                pairr[secondd[i]] += (1 << b);
                continue;
            }

            int prevAns = ans;
            ans = Query( secondd[i] );
            inSet[secondd[i]] ^= 1;

            if ( ans == prevAns )
                pairr[secondd[i]] += (1 << b);
            else
                g1--;
        }
    }
}

void Solve( int n ) {
    vector <int> v;
    for ( int i = 1; i <= 2 * n; i++ ) {
        v.push_back( i );
        perm[i] = i;
    }
   // random_shuffle( perm + 1, perm + 1 + 2 * n );

    int prevAns = 0;
    for ( int i = 1; i <= 2 * n; i++ ) {
        if ( firstt.size() == n ) {
            secondd.push_back( perm[i] );
            continue;
        }

        ans = Query( perm[i] );
        inSet[perm[i]] = true;
        if ( ans > prevAns )
            firstt.push_back( perm[i] );
        else
            secondd.push_back( perm[i] );
        prevAns = ans;
    }

    solve( n );

    for ( int i = 0; i < n; i++ )
        Answer( secondd[i], firstt[pairr[secondd[i]]] );
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:58:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         if ( firstt.size() == n ) {
      |              ~~~~~~~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 6 ms 1232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 6 ms 1232 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1232 KB Output is correct
15 Correct 16 ms 2988 KB Output is correct
16 Incorrect 17 ms 2652 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -