Submission #1305798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305798		benight	Lost Array (NOI19_lostarray)	C++20	26 / 100	8 ms	1988 KiB

lostarray

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<ll>
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fa(e,l) for(auto e:l)
#define all(arr) arr.begin(),arr.end()

// int dfs(ll i,vi& visited,vector<vi>& adj,vi& trip,ll par){
//     fa(e,adj[i]){
//         if(e==par){continue;}
//         if(visited[e]==0){return e;}
//         else{
//             visited[e]=0;
//             ll a=dfs(e,visited,adj,trip,i);
//             if(a!=-1){return a;}
//         }
//     }
//     return -1;
// }
// int bfs(){return 0;}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k,m=0,q;
    ll a,b,c,d=0,f,g;
    ll x,y,z;
    ll w;
    ll p,r,t,u,l;
    ll MOD=1000000007;
    ll INF=1e16;
    ll T;
    ll t2,t1,x1,x2,y1,y2;
    // cin>>T;
    T=1;
    f(I,0,T){
        cin>>n>>m;
        // string s;
        // cin>>s;
        ll ans=0;
        vi arr(n,-1);
        vector<tuple<ll,ll,ll>> q;
        f(i,0,m){
            cin>>a>>b>>c;
            q.pb({c,a,b});
        }
        sort(all(q));
        f(i,0,m){
            tie(c,a,b)=q[i];
            arr[a-1]=max(c,arr[a-1]);
            arr[b-1]=max(c,arr[b-1]);
        }
        fa(e,arr){
            if(e==-1){cout<<"1 ";}
            cout<<e<<" ";
        }

    }
}
/*
5 5
For odd pi, put pi+1/2 into winning class
For even pi, put pi/2+1 into winning class

If possible, nice

If total sum of x+y is >=sum of all pi
And if x-y>=total wins of A-total wins of B, then true


2x2
x3x

111x
xxx1

22
xx

xxxx   Inchresting
2222

26
x

23
xx
















kx+1
Addition is constant
It doesnt change
So at each new gate +x
x will be added no matter the amount of people
*2 or *3
So lets say
For each gate

  2 3 2 3 2
  3 3 3 3 3
  4 
  2
1 x a c e g
1 y b d f h

1*(rest of multiples top - 5)
1*(rest of multiples bottom -5)

In the first case, here is one possible way to play this game optimally.

Initially, we have l=1
 person in the left lane and r=1
 person in the right lane.

After passing through the first pair of gates, we gain 4
 people from the left gate and 1⋅(2−1)=1
 person from the right gate, for a total of 4+1=5
 people. We allocate 2
 people to the left lane and 3
 people to the right lane. This results in l=1+2=3
 people in the left lane and r=1+3=4
 people in the right lane.

After passing through the second pair of gates, we gain 3⋅(3−1)=6
 people from the left gate and 4⋅(3−1)=8
 people from the right gate, for a total of 6+8=14
 people. We allocate 7
 people to the left lane and 7
 people to the right lane. This results in l=3+7=10
 people in the left lane and r=4+7=11
 people in the right lane.

After passing through the last pair of gates, we gain 7
 people from the left gate and 4
 people from the right gate, for a total of 7+4=11
 people. We allocate 6
 people to the left lane and 5
 people to the right lane. This results in l=10+6=16
 people in the left lane and r=11+5=16
 people in the right lane.

At the end, the total number of people is 16+16=32
.

*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 48