oj.uz

Submission #372989

# Submission time Handle Problem Language Result Execution time Memory
372989 2021-03-02T22:19:42 Z AmineWeslati Hiring (IOI09_hiring) C++14
50 / 100
 1500 ms 13308 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
#define int ll
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

int N,W; 
vi S(MX),Q(MX);

bool check(int x, int y, int xx, int yy){
	return yy*x-xx*y<0;
}

int32_t main() {
    boost; IO();

    cin>>N>>W;
    FOR(i,1,N+1) cin>>S[i]>>Q[i];

    int ans=0,x=0,y=1; 
    vi vec;

    FOR(i,1,N+1){
    	int s=S[i],q=Q[i];
    	vpi v;
    	vi chosen;
    	FOR(j,1,N+1) if(S[i]*Q[j]>=S[j]*Q[i]) v.eb(S[i]*Q[j],j);
    	sort(all(v));

    	int cnt=0,cur=0;
    	for(auto it: v){
    		int x=it.fi,idx=it.se;
    		if(cur+x>W*Q[i]) break;
    		cnt++,
    		cur+=x;
    		chosen.pb(idx);
    	}

    	if(ckmax(ans,cnt) || (ans==cnt && check(cur,Q[i],x,y))){
    		tie(x,y)={cur,Q[i]};
    		vec.assign(all(chosen));
		}
		/*if(i==1){
			dbg(cur)
			dbgv(chosen)
		}*/
		dbgs(x,y)
    }
    cout << ans << endl;
    for(auto x: vec) cout << x << ' '; cout << endl;
    

    return 0;
}
//Change your approach

Compilation message

hiring.cpp: In function 'int32_t main()':
hiring.cpp:73:10: warning: unused variable 's' [-Wunused-variable]
   73 |      int s=S[i],q=Q[i];
      |          ^
hiring.cpp:73:17: warning: unused variable 'q' [-Wunused-variable]
   73 |      int s=S[i],q=Q[i];
      |                 ^
hiring.cpp:99:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   99 |     for(auto x: vec) cout << x << ' '; cout << endl;
      |     ^~~
hiring.cpp:99:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |     for(auto x: vec) cout << x << ' '; cout << endl;
      |                                        ^~~~

Subtask #1
20.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 2 ms 3436 KB Output is correct
5 Correct 3 ms 3436 KB Output is correct
6 Correct 82 ms 3564 KB Output is correct
7 Correct 190 ms 3692 KB Output is correct
8 Correct 352 ms 3564 KB Output is correct
9 Correct 675 ms 3908 KB Output is correct
10 Correct 1188 ms 4020 KB Output is correct
11 Execution timed out 1511 ms 4116 KB Time limit exceeded
12 Execution timed out 1597 ms 3980 KB Time limit exceeded
13 Execution timed out 1598 ms 4036 KB Time limit exceeded
14 Execution timed out 1594 ms 4316 KB Time limit exceeded
15 Execution timed out 1571 ms 4204 KB Time limit exceeded

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Execution timed out 1593 ms 4728 KB Time limit exceeded
5 Execution timed out 1591 ms 7520 KB Time limit exceeded
6 Runtime error 53 ms 9068 KB Execution killed with signal 11
7 Runtime error 46 ms 8940 KB Execution killed with signal 11

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3436 KB Output is correct
2 Correct 13 ms 3436 KB Output is correct
3 Correct 12 ms 3436 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3712 KB Output is correct
2 Correct 23 ms 3564 KB Output is correct
3 Correct 23 ms 3564 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3564 KB Output is correct
2 Correct 40 ms 3692 KB Output is correct
3 Correct 39 ms 3564 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 9492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1594 ms 13308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 9068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 9068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -