oj.uz

Submission #889420

# Submission time Handle Problem Language Result Execution time Memory
889420 2023-12-19T16:06:01 Z Alfraganus Gift (IZhO18_nicegift) C++17
7 / 100
 2000 ms 524288 KB 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 998244353;

set<vector<int>> s;
vector<pair<int, pair<int, int>>> ans;

bool dfs(vector<int> a){
    if(s.find(a) != s.end())
        return false;
    for(int i = 0; i < a.size(); i ++){
        if(a[i] > 0)
            break;
        if(i == a.size() - 1)
            return true;
    }
    s.insert(a);
    for(int i = 0; i < a.size(); i ++){
        for(int j = i + 1; j < a.size(); j ++){
            for(int x = min(a[i], a[j]); x >= 1; x --){
                a[i] -= x;
                a[j] -= x;
                if(dfs(a)){
                    ans.push_back({x, {i + 1, j + 1}});
                    return true;
                }
                a[i] += x;
                a[j] += x;
            }
        }
    }
    return false;
}

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    dfs(a);
    if(ans.size() == 0){
        cout << -1;
        return;
    }
    else{
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i ++)
            cout << ans[i].fs << ' ' << ans[i].ss.fs << ' ' << ans[i].ss.ss << endl;
    }
}

signed main()
{
    fastio int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Compilation message

nicegift.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
nicegift.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      | 
nicegift.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize(Ofast)
      | 
nicegift.cpp: In function 'bool dfs(std::vector<long long int>)':
nicegift.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < a.size(); i ++){
      |                    ~~^~~~~~~~~~
nicegift.cpp:37:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if(i == a.size() - 1)
      |            ~~^~~~~~~~~~~~~~~
nicegift.cpp:41:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < a.size(); i ++){
      |                    ~~^~~~~~~~~~
nicegift.cpp:42:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j = i + 1; j < a.size(); j ++){
      |                            ~~^~~~~~~~~~
nicegift.cpp: In function 'void solve()':
nicegift.cpp:71:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i = 0; i < ans.size(); i ++)
      |                        ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 456 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 0 ms 348 KB n=2

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 456 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 0 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Execution timed out 2083 ms 7948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 456 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 0 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Execution timed out 2083 ms 7948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1022 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 456 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 0 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Execution timed out 2083 ms 7948 KB Time limit exceeded
9 Halted 0 ms 0 KB -