#include <cstdio> #include <algorithm> using namespace std; const int N = 100005; int D[N], G[N]; int good[N], bad[N], go, ba; bool cmpg( int a, int b ) { if ( D[a] == D[b] ) return a < b; return D[a] < D[b]; } bool cmpb( int a, int b ) { if ( G[a] == G[b] ) return a < b; return G[a] < G[b]; } int main() { int n; long long int p, k; scanf("%d%lld",&n,&p); k = p; for (int i=0;i<n;i++) { scanf("%d%d",&D[i],&G[i]); k += G[i] - D[i]; if (G[i] >= D[i]) good[ go++ ] = i; else bad[ ba++ ] = i; } sort( good, good + go, cmpg ); sort( bad, bad + ba, cmpb ); bool mozna = 1; for (int i=0;i<go;i++) { p -= D[ good[ i ] ]; if ( p <= 0 ) mozna = 0; p += G[ good[ i ] ]; } for (int i=0;i<ba;i++) { k -= G[ bad[ i ] ]; if ( k <= 0 ) mozna = 0; k += D[ bad[ i ] ]; } if ( mozna ) { printf("TAK\n"); for (int i=0;i<go;i++) printf("%d ",good[i]+1); for (int i=ba-1;i>=0;i--) printf("%d ",bad[i]+1); printf("\n"); } else printf("NIE\n"); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <cstdio> #include <algorithm> using namespace std; const int N = 100005; int D[N], G[N]; int good[N], bad[N], go, ba; bool cmpg( int a, int b ) { if ( D[a] == D[b] ) return a < b; return D[a] < D[b]; } bool cmpb( int a, int b ) { if ( G[a] == G[b] ) return a < b; return G[a] < G[b]; } int main() { int n; long long int p, k; scanf("%d%lld",&n,&p); k = p; for (int i=0;i<n;i++) { scanf("%d%d",&D[i],&G[i]); k += G[i] - D[i]; if (G[i] >= D[i]) good[ go++ ] = i; else bad[ ba++ ] = i; } sort( good, good + go, cmpg ); sort( bad, bad + ba, cmpb ); bool mozna = 1; for (int i=0;i<go;i++) { p -= D[ good[ i ] ]; if ( p <= 0 ) mozna = 0; p += G[ good[ i ] ]; } for (int i=0;i<ba;i++) { k -= G[ bad[ i ] ]; if ( k <= 0 ) mozna = 0; k += D[ bad[ i ] ]; } if ( mozna ) { printf("TAK\n"); for (int i=0;i<go;i++) printf("%d ",good[i]+1); for (int i=ba-1;i>=0;i--) printf("%d ",bad[i]+1); printf("\n"); } else printf("NIE\n"); } |