Submission #1286985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286985		cowkim	Art Collections (BOI22_art)	C++20	100 / 100	695 ms	464 KiB

art

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iomanip>
#include <vector>
#define ll long long
#define endl "\n"
using namespace std;
/**
 * returns how many complaints you will receive for this ordering of the art collections
 */
int publish(std::vector<int>);

/**
 * use this function when you have found the correct order of the art collections
 * You must call answer exactly once; your program will be automatically
 * terminated afterwards.
 */
void answer(std::vector<int>);

/**
 * implement this function
 */
// vector<int> actualperm;
// int publish(vector<int> perm){
//     cout << "? ";
//     for(auto num : perm){
//         cout << num << " ";
//     } 
//     cout << endl;
//     int ans = 0;
//     for(int i = 0; i<perm.size(); i++){
//         for(int j = 0; j < i; j++){
//             for(int z = actualperm.size()-1; actualperm[z] != perm[i]; z--){
//                 if(actualperm[z] == perm[j]){
//                     ans++;
//                     break;
//                 }
//             }
//         }
//     }
//     cout << ans << endl;
//     return ans;
// }
// void answer(vector<int> perm){
//     cout << "! ";
//     for(auto num : perm){
//         cout << num << " ";
//     } 
//     cout << endl;
// }
// 1 2 3 4 5 6 7
// 7 1 2 3 4 5 6
//1:6 + lessthen 7
//1:6 + morethen 7
//less - more
//less + more = n-1
//2*less = q + n-1
//less = (q + n-1)/2
void solve(int n){
    vector<int> permAns(n);
    for(int shift = 0; shift < n; shift++){
        vector<int> permutation(n);
        for(int i = 1; i<=n; i++){
            permutation[(i+shift-1)%n] = i;
        }
        permAns[shift] = publish(permutation);
    }
    vector<int> ans(n);
    for(int i = 1; i<= n; i++){
        //när den är sist = n - i
        //när den är först = (sist +1)%n = 0
        //cout << "solving " << i << endl;
        int lasti = n-i;
        int firsti = (lasti +1)%n;
        //cout << lasti << " " << firsti << endl;;
        int firstVal = permAns[firsti];
        int lastVal = permAns[lasti];
        //cout << lastVal << " " << firstVal << endl;
        int diff = lastVal - firstVal;
        //cout << diff << endl;
        int less = (diff + n-1)/2;
        //cout << "( " << diff << " + " << n-1 << " ) / 2" << endl;
        //cout << less << endl;
        ans[n-less-1] = i;
    }
    answer(ans);
}
// int main(){
//     int n;
//     cin >> n;
//     actualperm.resize(n);
//     for(int i = 0; i<n; i++){
//         cin >> actualperm[i];
//     }
//     solve(n);
// }
// 5 3 7 2 6 1 4

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30